fibonacci数列について

みんな大好きfibonacci数列。名前だけでも聞いたことがある人は割といると思います。さて、どんな数列かというと漸化式で \begin{align} a_n = a_{n-1}+a_{n-2}\\ \nonumber a_0 = 0,a_1=1 \end{align} とあらわされるのがfibonacci数列です。\( F_0,F_1 \)をどうするかはいろいろと流派があります。ここでは、上記のように扱います。
具体的に書くと \begin{align} 0,1,1,2,3,5,8,13,21,34,55,\cdots \end{align}

一般項

fibonacci数列の一般項は次のようになります。 \begin{align} a_n = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right\} \end{align} 漸化式は整数の足し算のみであらわされるのに、一般項は無理数が出てくるという。なんとも不思議な形。これを導出してみます。
まず、fibonacci数列を母関数というものに対応付けます。その母関数をいろいろいじくり回して、一般項を得るという流れです。

母関数

。 数列\( a_0,a_1,a_2.\cdots \)に対して、母関数\( F(x) \)とは \begin{align} F(x) &=& a_0 + a_1 x + a_2 x^2 + \cdots \\ &=& \sum_{i=0}^\infty a_i x^i \end{align} のことを言います。べき級数の各係数に数列の各項の値が対応しています。

fibonacci数列の一般項を導出する。

fibonacci数列の母関数\( F(x) \)をいじくってみましょう。fibonacci数列の漸化式\( a_n = a_{n-1} + a_{n-2} \)をもとに、\( x^2 F(x) + x F(x) \)について考えます。 \begin{align} x^2 F(x) + x F(x) &=& a_0x + (a_0 + a_1)x^2 + (a_1 + a_2)x^3 + \cdots\\ &=& a_0x + a_2 x^2 + a_3x^3 + \cdots\\ &=& a_0x + (F(x) - a_1 x - a_0)\\ &=& F(x) - x \end{align} 以上より、次のようにfibonacci数列の母関数をべき級数の形から変形できます。 \begin{align} F(x) &=& \frac{x}{1- x - x^2 }\\ &=& \frac{x}{(1 - \omega_1 x)(1 - \omega_2 x)}\\ \nonumber \omega_1 = \frac{1 + \sqrt{5}}{2}\\ \nonumber \omega_2 = \frac{1 - \sqrt{5}}{2} \end{align} なにやら無理数\( \sqrt{5} \)がでてきました!
さて、次は\( F(x) \)を部分分数分解して、形を変形します。 \begin{align} F(x) &=& \frac{x}{(1 - \omega_1 x)(1 - \omega_2 x)}\\ &=& \frac{\frac{1}{\omega_1 - \omega_2}}{1 - \omega_1 x} + \frac{\frac{-1}{\omega_1 - \omega_2}}{1 - \omega_2 x}\\ &=& \frac{1}{\omega_1 - \omega_2} \left( \frac{1}{1 - \omega_1 x} - \frac{1}{1 - \omega_2 x} \right) \end{align} ここで、思い出してほしいのが\( \frac{1}{1-x} \) のTaylor展開が \( 1 + x + x^2 + \cdots \)であること。複素関数で特異点を求めるときとかによく出てきます。これをさっきの式に適用するとべき級数の形に戻せます。 \begin{align} F(x) &=& \frac{1}{\omega_1 - \omega_2} \left( \frac{1}{1 - \omega_1 x} - \frac{1}{1 - \omega_2 x} \right)\\ &=& \frac{1}{\omega_1 - \omega_2} \left( (1+\omega_1 x + (\omega_1 x)^2 + \cdots) - (1 + \omega_2 x + (\omega_2 x)^2 + \cdots) \right)\\ &=& 0 + \frac{\omega_1 - \omega_2}{\omega_1 - \omega_2}x + \frac{\omega_1^2 - \omega_2^2}{\omega_1 - \omega_2}x^2 + \cdots + \frac{\omega_1^n - \omega_2^n}{\omega_1 - \omega_2}x^n + \cdots \end{align}
これの各係数がfibonacci数列の各項でしたね。よって、一般項は \begin{align} a_n &=& \frac{\omega_1^n - \omega_2^n}{\omega_1 - \omega_2}\\ &=&\frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right\}\\ \nonumber & &\mathrm{where}\ \ \ \omega_1 = \frac{1 + \sqrt{5}}{2},\omega_2 = \frac{1 - \sqrt{5}}{2}\\ \end{align} となります。あの世(母関数)に飛ばしていじくってたら出てきたみたいな感じ。
質問、コメントなどはこちら