フィボナッチ数列の一般項を求める

フィボナッチ数列は、

$\displaystyle F_0 =0, F_1 = 1, \, F_{n+2} = F_{n+1} + F_n \, (n = 0, 1, 2, \ldots)$

という漸化式で与えられる数列。具体的な値は、

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, \ldots$

である。この数列の一般項を知った時は驚いた。

「数学ガール」(シリーズ第1作)では母関数を用いて一般項を導出していたが、等比数列に帰着する方法でガリガリと求めることもできる。

$\displaystyle F_{n+2} - \alpha F_{n+1} = \beta(F_{n+1} - \alpha F_n) \quad(*1)$

がすべての $n$ に対して成り立つとすると

$\displaystyle F_{n+2} = (\alpha + \beta)F_{n+1} - \alpha \beta F_n$

となるので、フィボナッチ数列の定義と比較して

$\displaystyle \alpha + \beta = 1, \, \alpha \beta = -1$

これを解くと $\displaystyle \alpha, \beta = \frac{1 \pm \sqrt{5}}{2}$

どちらを $\alpha$ としてもよいが、 $\displaystyle \alpha = \frac{1 - \sqrt{5}}{2}, \beta = \frac{1 + \sqrt{5}}{2}$ とする。(*1)の形から $A_n = F_{n+1} - \alpha F_n$ とおくと、

$\displaystyle A_0 = F_1 - \alpha F_0 = 1$

$A_{n+1} = \beta A_n$

$\displaystyle \therefore A_n = \beta^n$

$\displaystyle \therefore F_{n+1} - \alpha F_n = \beta^n\quad(*2)$

$F_n$ に関する等比数列を導くために $F_{n+1} - \beta \gamma = \alpha (F_n - \gamma)$ とおくと

$\displaystyle F_{n+1} - \alpha F_n = (\beta - \alpha) \gamma$

これを(*2)と比較して

$\displaystyle (\beta - \alpha) \gamma = \beta^n$

$\displaystyle \therefore \gamma = \frac{\beta^n}{\beta-\alpha}$

$\displaystyle \therefore F_{n+1} - \frac{\beta^{n+1}}{\beta-\alpha} = \alpha(F_n - \frac{\beta^n}{\beta-\alpha})$

$\displaystyle B_n = F_n - \frac{\beta^n}{\beta-\alpha}$ とおくと

$\displaystyle B_0 = F_0 - \frac{1}{\beta-\alpha} = - \frac{1}{\beta-\alpha}$

$\displaystyle B_{n+1} = \alpha B_n$

$\displaystyle \therefore B_n = \frac{- \alpha^n}{\beta-\alpha}$

$\displaystyle \therefore F_n - \frac{\beta^n}{\beta-\alpha} = \frac{- \alpha^n}{\beta-\alpha}$

$\displaystyle \therefore F_n = \frac{1}{\beta - \alpha} (\beta^n - \alpha^n)$

$\displaystyle \alpha = \frac{1 - \sqrt{5}}{2}, \beta = \frac{1 + \sqrt{5}}{2}$ を代入して計算すると

$\displaystyle 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項 $\displaystyle - \frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^n$ の絶対値は $n = 1$ のときの値 $0.27639\ldots$ が最大で、どんどん小さくなっていく。これが常に $0.5$ より小さいことから、フィボナッチ数列の一般項は、床関数を用いて