📂レンマ

フィボナッチ数列の一般項の導出

定理

シーケンス $\left\{ F_{n} \right\}_{n=0}^{\infty}$が$F_{n+1} := F_{n} + F_{n-1}$として定義されるとしよう。$F_{0} = F_{1} = 1$ならば$\displaystyle r_{0} : = {{1 + \sqrt{5} } \over {2}}$と$\displaystyle r_{1} : = {{1 - \sqrt{5} } \over {2}}$について $$F_{n} = {{ {r_{0}}^{n+1} - {r_{1}}^{n+1} } \over { r_{0} - r_{1} }}$$

説明

• 上で紹介されたフィボナッチ数列が$0$項から始まることに注意しよう。

フィボナッチ数列の一般項はビネの公式^{binet formula}とも呼ばれる。フィボナッチ数列は多くの性質を持っており、予想もしない部分で応用されることもある。フィボナッチ数列だけで本が出ているほどで、教科書やインターネットでも説明が多いので、ここでは省略することにする。

導出

式 $$\begin{align*} & r^2 - r - 1 \\ =& \left( r - {{1 + \sqrt{5} } \over {2}} \right) \left( r - {{1 - \sqrt{5} } \over {2}} \right) \\ =& ( r - r_{0} ) ( r - r_{1} ) \end{align*}$$ を考えよう。この式によると $${r_{0}}^2 - {r_{0}} - 1 = 0 \\ {r_{1}}^2 - {r_{1}} - 1 = 0$$が成り立つ。もう少し見栄え良く変えると $${r_{0}}^2 = {r_{0}} + 1 \\ {r_{1}}^2 = {r_{1}} + 1$$だ。ここで数学的帰納法を使用して $$F_{n} = {{ {r_{0}}^{n+1} - {r_{1}}^{n+1} } \over { r_{0} - r_{1} }}$$が真であることを示す。

---

$n=0$のとき、 $$F_{0} = {{ {r_{0}}^{0+1} - {r_{1}}^{0+1} } \over { r_{0} - r_{1} }} = 1$$

---

$n=1$のとき、 $$F_{1} = {{ {r_{0}}^{1+1} - {r_{1}}^{1+1} } \over { r_{0} - r_{1} }} = 1$$

---

$n=k$と仮定すると $$F_{k} = {{ {r_{0}}^{k+1} - {r_{1}}^{k+1} } \over { r_{0} - r_{1} }}$$が成り立つ。

$\left\{ F_{k} \right\}$はフィボナッチ数列なので、

$$\begin{align*} F_{k+1} =& F_{k} + F_{k-1} \\ =& {{ {r_{0}}^{k+1} - {r_{1}}^{k+1} } \over { r_{0} - r_{1} }} + {{ {r_{0}}^{k} - {r_{1}}^{k} } \over { r_{0} - r_{1} }} \\ =& {{ {r_{0}}^{k} ( r_{0} + 1 ) - {r_{1}}^{k} ( r_{1} + 1 ) } \over { r_{0} - r_{1} }} \\ =& {{ {r_{0}}^{k} \cdot { r_{0} }^{2} - {r_{1}}^{k} \cdot { r_{1} }^{2} } \over { r_{0} - r_{1} }} & \because {r_{0}}^2 = {r_{0}} + 1, {r_{1}}^2 = {r_{1}} + 1 \\ =& {{ {r_{0}}^{k+2} - {r_{1}}^{k+2} } \over { r_{0} - r_{1} }} \end{align*}$$ まとめると、 $$F_{k+1} = {{ {r_{0}}^{k+2} - {r_{1}}^{k+2} } \over { r_{0} - r_{1} }}$$ であり、これは $$F_{n} = {{ {r_{0}}^{n+1} - {r_{1}}^{n+1} } \over { r_{0} - r_{1} }}$$が$n=k+1$のときにも成り立つということだ。

■