フィボナッチ数[1]

\((1)\)  フィボナッチの漸化式
\begin{cases}
F_1=1  , F_2=1\\
F_{n+2}=F_{n+1}+F_n
\end{cases}
この漸化式を解くことで、次の一般項(ビネの公式)が得られます。
$$F_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}$$

\((2)\) フィボナッチ数の母関数$$g(x)=\displaystyle\sum_{n=0}^{\infty} F_n x^n=\frac{x}{1-x-x^2}$$








<証明>

\((1)\) \(F_{n+2}-F_{n+1}-F_n=0\) (三項間漸化式の特性方程式を解きます。)
$$\displaystyle x^2-x-1=0, x=\frac{1 \pm \sqrt{5}}{2}$$二つの解を次のように \(α,β\) とします。$$ \displaystyle α=\frac{1-\sqrt{5}}{2} ,  β=\frac{1+\sqrt{5}}{2}$$すると元の漸化式は次のように表せます。
\begin{cases}
F_{n+2}-αF_{n+1}=β(F_{n+1}-αF_n)\\
F_{n+2}-βF_{n+1}=α(F_{n+1}-βF_n)
\end{cases} それぞれ解くと
\begin{cases}
F_{n+1}-αF_n=β^{n-1}(F_2-αF_1)   \cdots(A)\\
F_{n+1}-βF_n=α^{n-1}(F_2-βF_1)   \cdots(B)
\end{cases}\((A)-(B)\) を計算します。$$(β-α)F_n=β^{n-1}(F_2-αF_1)-α^{n-1}(F_2-βF_1) $$ 上の式を部分的に計算すると
$$ F_2-αF_1=1-\frac{1-\sqrt{5}}{2}=\frac{1+\sqrt{5}}{2}=β$$$$ F_2-βF_1=1-\frac{1+\sqrt{5}}{2}=\frac{1-\sqrt{5}}{2}=α$$$$ β-α=\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}=\sqrt{5}$$よって元の式は \(\sqrt{5}F_n=β^n-α^n\) となるので、以上より$$F_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\} $$

またフィボナッチ数列の公比の極限は黄金比 \(\displaystyle \frac{1+\sqrt{5}}{2}\) に収束します。

<証明>

$$\displaystyle\lim_{n \to \infty}\frac{F_{n+1}}{F_n}=\displaystyle\lim_{n \to \infty} \frac{β^{n+1}-α^{n+1}}{β^n-α^n}=\displaystyle\lim_{n \to \infty} \frac{β-α\left(\frac{α}{β}\right)^n}{1-\left(\frac{α}{β}\right)^n}$$$$(β \gt α)   \displaystyle\lim_{n \to \infty}\frac{F_{n+1}}{F_n}=β=\frac{1+\sqrt{5}}{2}$$







\((2)\) 形式上 \(F_0=0\) とすれば、母関数の級数は次のようになります。$$g(x)=\displaystyle\sum_{n=0}^{\infty} F_nx^n=F_0+F_1x+F_2x^2+F_3x^3+F_4x^4+ \cdots  (C)$$両辺に \(x\) を掛けます。$$xg(x)=F_0x+F_1x^2+F_2x^3+F_3x^4+F_4x^5+ \cdots  (D)$$\((C)+(D)\) を計算します。
\begin{alignat}{2}
g(x)+xg(x)&=F_0+(F_0+F_1)x+(F_1+F_2)x^2+(F_2+F_3)x^3+(F_3+F_4)x^4+ \cdots \\
&\\
&=F_2x+F_3x^2+F_4x^3+F_5x^4+F_6x^5+ \cdots\\
\end{alignat}両辺に \(F_1=1\) を加えます。$$(1+x)g(x)+1=F_1+F_2x+F_3x^2+F_4x^3+F_5x^4+F_6x^5+ \cdots$$両辺に \(x\) を掛けます。$$x(1+x)g(x)+x=F_1x+F_2x^2+F_3x^3+F_4x^4+F_5x^5+F_6x^6+ \cdots$$右辺に \(F_0\,(=0)\) を用意します。$$x(1+x)g(x)+x=F_0+F_1x+F_2x^2+F_3x^3+F_4x^4+F_5x^5+F_6x^6+ \cdots=g(x)$$ 移行して整理します。$$g(x)=x(1+x)g(x)+x,  (1-x-x^2)g(x)=x$$両辺を \(1-x-x^2\) で割ります。以上より$$g(x)=\displaystyle\sum_{n=0}^{\infty} F_n x^n=\frac{x}{1-x-x^2}$$

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です