フィボナッチ数列の一般項の導出
定理
シーケンス $\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$のときにも成り立つということだ。
■