フィボナッチ数列を解く

1,1,2,3,5,8,13,21,34.55,...,と続いていく数列をフィボナッチ(Fibonacci)数列といいます。

　これは前の２つの数を加えたものが次の数になるという数列

であり,漸化式:ａ_n+2＝ａ_n+1＋ａ_n(ｎ≧1,ａ₁＝1,ａ₂＝1)で定義

されます。

　　図形的には,環状列石(StoneーHenge;ストーンヘンジ)や生物

の巻貝(アンモナイトetc.)などに見られるファイ螺旋,美術に

おいて有名な黄金分割の構成を示すものでもあります。

　この数列のｎによる一般項の表現を,高校生のときのような

方法で解いても面白味がないので,関数方程式の行列表現として

解いてみます。

　　まあ結局は同じことで,内容は陳腐な試みですが。。

　　先に述べたようにフィボナッチ数列を定める漸化式は

ａ_n+2＝ａ_n+1＋ａ_n(ｎ≧1,ａ₁＝1,ａ₂＝1)で与えられますが,

これは行列形式では次のように書けます。

　　すなわち,Ａ_n≡^t[ａ_n,ａ_n+1],Ｐ≡[Ｐ₁,Ｐ₂];Ｐ₁≡^t[0,1],

Ｐ₂≡^t[1,1]と置けば,フィボナッチ数列の漸化式はＡ_n+1＝ＰＡ_n

と書けます。

それ故,Ａ_n＝Ｐ^n-1Ａ₁となります。

ただし,上添字ｔは転置行列(transport matrix)を意味します。

例えば^t[0,1]は行(横)ベクトル(１×２行列){0,1]を転置した

列(縦)ベクトル(２×１行列)を意味します。

ここで,固有値問題ＰＸ＝λＸを解きます。

これの解の固有値は固有値方程式:det(λＥ－Ｐ)＝0 を解けば

得られますが,この方程式は謂わゆる数列の特性方程式:

λ²－λ－1＝0 です。

この２次方程式の２つの根はλ_±≡(1±√5)/2ですが,このλ_±

が固有値問題ＰＸ＝λＸの固有値λの２つの値を与えます。

一方,固有値λ＝λ_±に属する固有ベクトルをＸ_±とすると定数倍を

別にしてＸ_±＝^t[1,λ_±]と書けます。

これらにより,ＰＸ_±＝λ_±Ｘ_±(複号同順)が成立します。

そこで,２×２行列ＢをＢ≡[Ｘ_＋,Ｘ_－]で定義すると,

ＰＢ＝[λ_＋Ｘ₊,λ_－Ｘ_－]です。

したがって,Λを固有値λ_±を対角成分とする２×２対角行列

とすると,ＰＢ＝ＢΛが成立します。

これから,Λ＝Ｂ^-1ＰＢ,Ｐ＝ＢΛＢ^-1であり,それ故,

Λⁿ＝Ｂ^-1ＰⁿＢ,Ｐⁿ＝ＢΛⁿＢ^-1が成立します。

Ａ_n＝Ｐ^n-1Ａ₁に戻り,これの左からＢ^-1を掛けると

Ｂ^-1Ａ_n＝(Ｂ^-1Ｐ^n-1Ｂ)Ｂ^-1Ａ₁＝Λ^n-1Ｂ^-1Ａ₁を得ます。

Ａ₁ ＝^t[1,1], Ｂ^-1Ａ₁ ＝^t[1－λ_－,－1＋λ_＋]/√5

＝^t[λ_＋,－λ_－]/√5ですから,Ｂ^-1Ａ_n＝^t[λ_＋ⁿ,－λ_－ⁿ]/√5　です。

以上から,Ａ_n＝^t[ａ_n,ａ_n+1]＝Ｂ^t[λ_＋ⁿ,－λ_－ⁿ]/√5より,最終的に

ａ_n＝(λ_＋ⁿ－λ_－ⁿ)/√5 が得られます。

(ネタがないからといって,16年前に予備校でやった計算を蒸し返して

いるなんて,我ながら全然進歩がないですね。)