フィボナッチ数列の7つの性質（一般項・黄金比・互いに素）

$F_{n}=F_{n-1}+F_{n-2}$ という漸化式を解きたい。

特性方程式 $x^2=x+1$ の解を $\alpha=\dfrac{1+\sqrt{5}}{2}, \beta=\dfrac{1-\sqrt{5}}{2}$ とおくと，$\alpha+\beta=1, \alpha\beta=-1$ より

$F_n=(\alpha+\beta)F_{n-1}-\alpha\beta F_{n-2}$

これを変形して，

$F_n-\alpha F_{n-1}=\beta(F_{n-1}-\alpha F_{n-2})$

よって，$F_n-\alpha F_{n-1}$ は公比 $\beta$ の等比数列となる：

$F_n-\alpha F_{n-1}=\beta^{n-2}(F_2-\alpha F_1)=\beta^{n-1}$

同様にして，

$F_n-\beta F_{n-1}=\alpha^{n-2}(F_2-\beta F_1)=\alpha^{n-1}$

この2式から $F_{n-1}$ を消去して $F_n$ について解く：

$F_n=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}\\ =\dfrac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right\}$

$n=1, n=2$ のときビネの公式が正しいことは簡単に確認できる。

$n=k, k+1$ のときにビネの公式が正しいと仮定すると，

$F_{k+2}=\dfrac{\alpha^{k+1}-\beta^{k+1}}{\alpha-\beta}+\dfrac{\alpha^{k}-\beta^{k}}{\alpha-\beta}=\dfrac{\alpha^{k+2}-\beta^{k+2}}{\alpha-\beta}$

($\because \alpha+1=\alpha^2, \beta+1=\beta^2)$

となり，$n=k+2$ のときも正しい。

性質1（ビネの公式）より，

$\displaystyle\lim_{n\to\infty}\dfrac{F_{n+1}}{F_n}=\lim_{n\to\infty}\dfrac{\alpha^{n+1}-\beta^{n+1}}{\alpha^n-\beta^n}=\alpha$

$(\because \alpha > \beta)$

$F_k$ と $F_{k-1}$ が共通の約数 $p\geq 2$ を持つと仮定すると，

$F_k=mp, F_{k-1}=np$
（ただし $m, n, p$ は整数）と書ける。

漸化式より，

$F_{k-2}=F_{k}-F_{k-1}=(m-n)p$

も $p$ の倍数なので，

$F_{k-1}$ と $F_{k-2}$ も共通因数 $p$ を持つ。

これを繰り返すと $F_2$ と $F_1$ も共通因数 $p$ を持つ。

これは $F_2=F_1=1$ に矛盾

• $n=1$ のとき，$F_{m+1}=F_{m-1}F_1+F_{m}F_2$ はフィボナッチ数列の漸化式そのものであり成立。

• $n=2$ のとき，フィボナッチ数列の漸化式を使うと
  $F_{m+2}=F_{m+1}+F_{m}\\ =F_{m-1}+2F_{m}\\ =F_{m-1}F_2+F_{m}F_{3}$
  となり成立。

• $n=k$ と $n=k-1$ の場合も正しいと仮定して $n=k+1$ の場合を計算すると，
  $F_{m+k+1}=F_{m+k}+F_{m+k-1}\\ =(F_{m-1}F_{k}+F_{m}F_{k+1})+(F_{m-1}F_{k-1}+F_{m}F_{k})\\ =F_{m-1}(F_{k}+F_{k-1})+F_{m}(F_{k+1}+F_{k})\\ =F_{m-1}F_{k+1}+F_{m}F_{k+2}$
  となり成立。