フィボナッチ数／リュカ数の一般項の計算について - 音楽室と化学室と美術室とPC室の融合部屋　所謂自由室

皆さんフィボナッチ数列はもちろん知っていますよね？

今回はフィボナッチ数列の一般項の計算について調べてみました．
問題設定自体は高校生でやるような内容ですが，色々調べたりはしたので備忘録的に書き連ねます．

フィボナッチ数列について
- フィボナッチ数列の漸化式
- 普通の出し方（概略）
フィボナッチ数列を計算する
参考文献

フィボナッチ数列ですが，皆さんよく知っている通り
$F_1 = 1,F_2 = 1$
$F_{n+2} = F_{n+1} + F_n$
という式で表される数列です．
この式自体は $F_1 = 1,F_2 = 1$ が与えられていて
$F_3 = F_2 + F_1 = 1+1 = 2$
$F_4 = F_3 + F_2 = 2+1 = 3$
と逐次的に計算していくと得られます．
リュカ数列は
$L_1 = 1,L_2 = 3$
$L_{n+2} = L_{n+1} + L_n$
で表される数式で，まぁフィボナッチ数列と似通っている数列です．

普通の出し方（概略）

$F_{n+2} = F_{n+1} + F_n$
から
$F_{n+2} - \alpha F_{n+1} = \beta(F_{n+1} - \alpha F_{n})$
という形に変形し
$F_{n+1} - \alpha F_{n} = a_n$
と置くなりなんなりして
$a_{n+1} = \beta a_n$
というような等比数列の形にしてやる．

一方
$F_{n+2} - \alpha F_{n+1} = \beta(F_{n+1} - \alpha F_{n})$
を変形した
$F_{n+2} = (\alpha + \beta)F_{n+1} - \alpha \beta F_{n}$
と
$F_{n+2} = F_{n+1} + F_n$
の係数比較から
$(\alpha + \beta) = 1$
$\alpha\beta = -1$
を得てあとは解と係数の関係から $\alpha,\beta$ を解いてやる．
得られる解2つどちらを $\alpha$ と $\beta$ にするかで二通りの等比数列の式が得られ，2つの等比数列の一般項を導出した後に，二式から $F_{n}$ のみの式を導出してやればよい．

フィボナッチ数列を計算する

計算の方針

ここで唐突ですが， $A,B$ を定数とする漸化式
$a_{n+2} = Aa_{n+1} + Ba_n$
について，
$a_{3} = Aa_{2} + Ba_1$
$a_{4} = Aa_{3} + Ba_2$
$a_{5} = Aa_{4} + Ba_3$
$\cdots$
といったような連立方程式と考えることができ，用いる変数は $a_1 ,a_2,a_3,\cdots$ となる．
仮に２つで打ち切った
$a_{3} = Aa_{2} + Ba_1$
$a_{4} = Aa_{3} + Ba_2$
としたら，式は2つなのに変数は4つの連立方程式になる．
未知数が2つなのでこれの一般項はパラメータを2つ用いて表すことができ， $a_1,a_2$ が設定されてようやく数値が確定する．
今回はパラメタを用いた式を導出して， $a_1,a_2$ を用いて一般項を確定するという流れでやってみたい．

重ね合わせの原理

ここで等比数列 $a_{n+1} = ra_n$ について
$a_n = C r^{n-1}$
という解はよくわかる．
この解となる数列を2つ， $b_n$ と $c_n$ を用意して
$a_n = \alpha b_n + \beta c_n$
としてもこの等比数列 $a_{n+1} = ra_n$ の性質を満たす．
$a_{n+1} = r(\alpha b_n + \beta c_n)$
$a_{n+1} = \alpha rb_n + \beta rc_n$
$a_{n+1} = \alpha b_{n+1} + \beta c_{n+1}$

別の式 $a_{n+2} = Aa_{n+1} + Ba_n$ についても同様の性質があるかを考える．
$a_{n+2} = Aa_{n+1} + Ba_n$ を満たす数列 $b_n,c_n$ が存在したとき
$a_n = \alpha b_n + \beta c_n$
も $a_{n+2} = Aa_{n+1} + Ba_n$ の解になる．
実際
$a_{n+2} = A(\alpha b_{n+1} + \beta c_{n+1}) + B(\alpha b_n + \beta c_n)$
$a_{n+2} = \alpha(Ab_{n+1} + Bb_n) + \beta(Ac_{n+1} + Bc_n)$
ここで $b_n,c_n$ は $a_{n+2} = Aa_{n+1} + Ba_n$ を満たすので
$a_{n+2} = \alpha b_{n+2} + \beta c_{n+2}$
が得られる．

フィボナッチ数列の計算

最初に
$F_{n+2} = F_{n+1} + F_n$
を満たす等比数列 $F_n$ について考える．
ここで等比数列の解 $F_n = r^{n-1}$ を代入する．
なぜ $F_n = Cr^{n-1}$ ではないかというと，
$Cr^{n+1} = Cr^{n} + Cr^{n-1}$
としても $C$ は自然消滅し，
$r^{n+1} = r^{n} + r^{n-1}$
結局のところ $F_n = r^{n-1}$ を代入することと変わらない．
$r \neq 0$ のとき
$r^{2} - r - 1 = 0$
となり，これを満たす $r$ を導出する．
今回は明らかに
$r = \frac{1 + \sqrt{5}}{2} , \frac{1 - \sqrt{5}}{2}$
になり，
$F_n = \left( \frac{1 + \sqrt{5}}{2} \right)^{n-1}$
$F_n = \left( \frac{1 - \sqrt{5}}{2} \right) ^ {n-1}$
の2つが $F_{n+2} = F_{n+1} + F_n$ の解になるので，重ね合わせした
$F_n = \alpha \left( \frac{1 + \sqrt{5}}{2} \right)^{n-1} + \beta \left( \frac{1 - \sqrt{5}}{2} \right)^{n-1}$
も $F_{n+2} = F_{n+1} + F_n$ の解になる．

こうして重ね合わせた結果と $F_1 = 1$ と $F_2 = 1$ について考えると
$F_1 = \alpha + \beta = 1$
$F_2 = \alpha \frac{1 + \sqrt{5}}{2} + \beta \frac{1 - \sqrt{5}}{2} = 1$
の $\alpha,\beta$ に対する連立方程式を解いて
$\alpha = \frac{1}{\sqrt{5}} \frac{1+\sqrt{5}}{2}$
$\beta = \frac{-1}{\sqrt{5}} \frac{1-\sqrt{5}}{2}$
代入すれば
$F_n = \frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^{n} - \frac{1}{\sqrt{5}}\left( \frac{1 - \sqrt{5}}{2} \right)^{n}$
良い．

リュカ数列の計算

フィボナッチ数列と漸化式は同じ
$L_{n+2} = L_{n+1} + L_n$
なので，同様にリュカ数列についても
$L_n = \alpha \left( \frac{1 + \sqrt{5}}{2} \right)^{n-1} + \beta \left( \frac{1 - \sqrt{5}}{2} \right)^{n-1}$
及び $L_1 = 1$ ， $L_2 = 3$ なので
$L_1 = \alpha + \beta = 1$
$L_2 =\alpha \frac{1 + \sqrt{5}}{2} + \beta \frac{1 - \sqrt{5}}{2} = 3$
から
$\alpha = \frac{1+\sqrt{5}}{2}$
$\beta = \frac{1-\sqrt{5}}{2}$
になるので
$L_n = \left( \frac{1 + \sqrt{5}}{2} \right)^{n} + \left( \frac{1 - \sqrt{5}}{2} \right)^{n}$
が得られる．