三項間漸化式

 $a_1=1$， $a_2=2$のとき，次の三項間漸化式を解く．$$a_n=a_{n-1}+a_{n-2}$$初期値を $a_0=1$， $a_1=1$として次の漸化式を解いても同様の結果を得られるので，計算簡素化のため，こちらを解くことにする．$$a_{n+1}=a_n+a_{n-1}\tag{0}$$ある実数$\alpha$と$\beta$を用いて(0)が次のように変形できれば，さらに下の(5)(6)のように変形できて漸化式が解けるので，$$a_{n+1}-\alpha a_n=\beta(a_n-\alpha a_{n-1})\tag{1}$$$$a_{n+1}-\beta a_n=\alpha(a_n-\beta a_{n-1})\tag{2}$$(1)と(2)をどちらも次式に変形し，$$a_{n+1}-(\alpha+\beta) a_n+\alpha\beta a_{n-1}=0\tag{3}$$(3)が(0)に一致することから係数比較すると，$\alpha+\beta=1$，$\alpha\beta=-1$ となるので，$\alpha$と$\beta$は次式 (特性方程式) の解であることがわかる．$$t^2-(\alpha+\beta)t+\alpha\beta=0\tag{4}$$$\alpha+\beta=1$ より $1-\alpha=\beta$，$1-\beta=\alpha$となるので，(1)と(2)は次のように変形できる．

$a_{n+1}-\alpha a_n=\beta(a_n-\alpha a_{n-1})=\dots=\beta^n(a_1-\alpha a_0)=\beta^n(1-\alpha)=\beta^{n+1}\tag{5}$

$a_{n+1}-\beta a_n=\alpha(a_n-\beta a_{n-1})=\dots=\alpha^n(a_1-\beta a_0)=\alpha^n(1-\beta)=\alpha^{n+1}\tag{6}$

(6)から(5)を引くと，$$(\alpha-\beta) a_n=\alpha^{n+1}-\beta^{n+1}$$$$a_n=\frac{1}{\alpha-\beta}(\alpha^{n+1}-\beta^{n+1})$$(4)の解を求めて$\alpha$と$\beta$の値を代入すれば求める第n項を得る．$$a_n=\frac{1}{\sqrt{5}}\left\{ \left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1} \right\}$$フィボナッチ数列の一般的な初期値 $a_0=0$， $a_1=1$なら第n項は次式になる．$$a_n=\frac{1}{\sqrt{5}}\left\{ \left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n} \right\}\tag{ビネの公式}$$