全脳科学帳

これを好む者はこれを楽しむ者に如かず

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

フィボナッチ数列は、

 \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 より小さいことから、フィボナッチ数列の一般項は、床関数を用いて

 \displaystyle F_n = \biggl\lfloor\frac{1}{\sqrt{5}} \left(\frac{1 + \sqrt{5}}{2}\right)^n + \frac{1}{2}\biggr\rfloor

と表すこともできる。