Ecasdqina's MEMO.

メモ帳.

フィボナッチ数列とかリュカ数列とか

きっかけ。

このツイートを見て遊んでみようと思った。

フィボナッチ数列とリュカ数列って?

両数列とも次の漸化式を満たす。
 a_{n}=a_{n-1}+a_{n-2}
違うのは初期値  a_{0} a_{1}の値
フィボナッチ数列の初期値は F_{0}=0, F_{1}=1
リュカ数列の初期値は L_{0}=2, L_{1}=1
となります。

一般項を導く

まず特性方程式 x^{2}=x+1を解き、その解をα,βと置きます、すると次の二式が成り立ちます。
 \alpha =\frac{1+\sqrt{5}}{2}
 \beta =\frac{1-\sqrt{5}}{2}
 \alpha +\beta =1, \alpha \beta =-1
この二式を使って初めの漸化式を変形すると。
 a_{n}=(\alpha +\beta)a_{n-1}-(\alpha \beta)a_{n-2}
整理すると。
 a_{n}-\beta a_{n-1}=\alpha (a_{n-1}-\beta a_{n-2})=\alpha ^{n-1}(a_{1}-\beta a_{0})
 a_{n}-\alpha a_{n-1}=\beta (a_{n-1}-\alpha a_{n-2})=\beta ^{n-1}(a_{1}-\alpha a_{0})
それぞれに \alpha ,\betaをかけて辺々引くと。
 (\alpha -\beta )a_{n}=\alpha ^{n}(a_{1}-\beta a_{0})-\beta ^{n}(a_{1}-\alpha a_{0})
 \Rightarrow a_{n}=\frac{1}{\sqrt{5}}(\alpha ^{n}(a_{1}-\beta a_{0})-\beta ^{n}(a_{1}-\alpha a_{0}))
一般項が導出できました! さて、この式にフィボナッチ数列かリュカ数列、あるいは他の数列(*)の初期値を与えればそれらの数列の一般項となります。
フィボナッチ数列の一般項は F_{n}=\frac{1}{\sqrt{5}}\left( \left( \frac{1+\sqrt{5}}{2}\right) ^{n}-\left( \frac{1-\sqrt{5}}{2}\right) ^{n}\right)
リュカ数列の一般項は L_{n}=\left( \frac{1+\sqrt{5}}{2}\right) ^{n}+\left( \frac{1-\sqrt{5}}{2}\right) ^{n}
やったぜ。 いえい!

感想とか

フィボナッチ数列の一般項を導こうと思って、なんとか \alpha \betaは出せたのですが、そこからがわからなかったので、この後は答えをチラ見しながら進めました。
後日リュカ数列の一般項を独力で導出してみたのですが、とても綺麗な形になったのでとても感動しました。

(*)  a_{n}=a_{n-1}+a_{n-2}の形の数列のみです。