フィボナッチ数列の漸化式・一般項・性質について

1. フィボナッチ数列の漸化式

2. 一般項

2.1. 一般項の求め方

$x^2-x-1=0$の解は$\displaystyle\frac{1\pm\sqrt{5} }{2}$であることから、大きいほうの解を$\alpha$、小さいほうの解を$\beta$とおく。以下の漸化式に変形することができる。

$$f_{n+2}-\alpha f_{n+1} = \beta(f_{n+1}-\alpha f_n)$$

$$f_{n+2}-\beta f_{n+1} = \alpha(f_{n+1}-\beta f_n)$$

それぞれ、$\lbrace f_{n+2}-\alpha f_{n+1}\rbrace$公比が$\beta$の等比数列、$\lbrace f_{n+2}-\beta f_{n+1} \rbrace$公比が$\alpha$の等比数列である。したがって、

$$f_{n+1}-\alpha f_{n} = \beta^{n}(f_{1}-\alpha f_{0})$$

$$\therefore f_{n+1}-\alpha f_{n} = \beta^{n}$$・・・①

$$f_{n+1}-\alpha f_{n} = \alpha^{n}(f_{1}-\beta f_{0})$$

$$\therefore f_{n+1}-\beta f_{n} = \alpha^{n}$$・・・②

よって、②-①をすると、$\alpha-\beta=\sqrt{5}$より、

$$\left(\alpha-\beta\right)f_{n}=\alpha^{n}-\beta^{n}$$

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

$$\therefore f_n = \displaystyle\frac{1}{\sqrt{5} }\left\{\left(\frac{1+\sqrt{5} }{2}\right)^n-\left(\frac{1-\sqrt{5} }{2}\right)^n\right\}$$

3. フィボナッチ数列の性質

3.1. 加法定理みたいな漸化式

3.1.1. 数学的帰納法を利用した証明

数学的帰納法を利用して証明します。

$[1]$$n=1$のときは、左辺は$f_{m+1}$、右辺は$f_{m+1}f_{1}+f_mf_{0}=f_{m+1}$となり、両辺が等しいことがわかります。 $[2]$$n=2$のときは、左辺は$f_{m+2}$、右辺は$f_{m+1}f_{2}+f_{m}f_{1}=f_{m+1}+f_{m}=f_{m+2}$となり、両辺が等しいことがわかります。
さらに、$n=k$、$n=k-1$のとき

$$f_{m+k}=f_{m+1}f_{k}+f_{m}f_{k-1}$$

$$f_{m+k-1}=f_{m+1}f_{k-1}+f_{m}f_{k-2}$$

式が成り立つと仮定する。

$[3]$$n=k+1$のとき、左辺は$f_{m+k+1}$、右辺は$f_{m+1}f_{k+1}+f_mf_k$です。ここで、フィボナッチ数列の漸化式を用いると、$f_{k+1}=f_k+f_{k-1}$、$f_{k}=f_{k-1}+f_{k-2}$、$f_{m+k}=f_{k+1}f_m+f_kf_{m-1}$が成り立つため、右辺を以下のように変形することができます。

$$f_{m+1}f_{k+1}+f_mf_k$$

$$= f_{m+1}(f_k+f_{k-1})+f_m(f_{k-1}+f_{k-2})$$

$$= f_{m+1}f_k+f_{m+1}f_{k-1}+f_mf_{k-1}+f_mf_{k-2}$$

ここで、仮定より、$f_{m+k}=f_{m+1}f_k+f_mf_{k-1}$と$f_{m+k-1}=f_{m+1}f_{k-1}+f_{m}f_{k-2}$が成り立つため、

$$f_{m+1}f_k+f_{m+1}f_{k-1}+f_mf_{k-1}+f_mf_{k-2}$$

$$=f_{m+1}f_k+f_mf_{k-1}+f_{m+1}f_{k-1}+f_mf_{k-2}$$

$$=f_{m+k}+f_{m+k-1}$$

フィボナッチ数列の漸化式より、$f_{m+k+1}=f_{m+k}+f_{m+k-1}$であるから、

$$=f_{m+k}+f_{m+k-1}$$

$$=f_{m+k+1}$$

よって、右辺と左辺が等しいため、$n=k+1$のときも成り立つ。

数学的帰納法により、$f_{m+k}=f_{m+1}f_{k}+f_{m}f_{k-1}$は成り立つ。

3.1.2. 一般項を用いた証明

$f_{n}=\displaystyle\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta}$を用いて証明を行う。

$$f_{m+1}f_{n}+f_{m}f_{n-1}$$

$$=\displaystyle\frac{\left(\alpha^{m+1}-\beta^{m+1}\right)\left(\alpha^{n}-\beta^{n}\right)}{\left(\alpha-\beta\right)^2}+\displaystyle\frac{\left(\alpha^{m}-\beta^{m}\right)\left(\alpha^{n-1}-\beta^{n-1}\right)}{\left(\alpha-\beta\right)^2}$$

$$=\displaystyle\frac{\alpha^{m+n+1}-\alpha^{m+1}\beta^{n}-\alpha^{n}\beta^{m+1}+\beta^{m+n+1}+\alpha^{m+n-1}-\alpha^{m}\beta^{n-1}-\alpha^{n-1}\beta^{m}+\beta^{m+n-1}}{\left(\alpha-\beta\right)^2}$$

$x^2-x-1=0$の解は$\displaystyle\frac{1\pm\sqrt{5} }{2}$であるため、解と係数の関係より、$\alpha+\beta=1$、$\alpha\beta=-1$である。

$\alpha\beta=-1$より、

$$\alpha^{m+1}\beta^{n}=-\alpha^{m}\beta^{n-1}$$

$$\alpha^{n}\beta^{m+1}=-\alpha^{n-1}\beta^{m}$$

であことと、$\alpha=-\displaystyle\frac{1}{\beta}$、$\beta=-\displaystyle\frac{1}{\alpha}$より、

$$=\displaystyle\frac{\alpha^{m+n+1}+\beta^{m+n+1}+\alpha^{m+n-1}+\beta^{m+n-1}}{\left(\alpha-\beta\right)^2}$$

$$=\displaystyle\frac{\alpha^{m+n}\left(\alpha+\displaystyle\frac{1}{\alpha}\right)+\beta^{m+n}\left(\beta+\displaystyle\frac{1}{\beta}\right)}{\left(\alpha-\beta\right)^2}$$

$$=\displaystyle\frac{\alpha^{m+n}\left(\alpha-\beta\right)-\beta^{m+n}\left(\alpha-\beta\right)}{\left(\alpha-\beta\right)^2}$$

$$=\displaystyle\frac{\alpha^{m+n}-\beta^{m+n}}{\alpha-\beta}$$

$$=f_{m+n}$$

となる。よって、$f_{m+n}=f_{m+1}f_{n}+f_{m}f_{n-1}$である。

3.2. 連続する２つのフィボナッチ数列の数の平方の和の漸化式

たとえば、$f_{5}=5$、$f_{6}=8$であるから、

$f_{5}^2+f_{6}^2$

$=25+64$

$=89$

$=f_{11}$

とのように、$f_{5}^2$と$f_{6}^2$の和は$f_{11}$になります。

証明は先ほどの漸化式を用いれば簡単に求めることができます。$m=n-1$のとき、

$$f_{m+n}=f_{m+1}f_{n}+f_{m}f_{n-1}$$

$$f_{2n-1}=f_{n}f_{n}+f_{n-1}f_{n-1}$$

$$\therefore f_{2n-1}=f_{n}^2+f_{n-1}^2$$

よって、$n=6$のときに、先ほど示した例のようになります。