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

$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$ について解くと $$\begin{aligned} 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\} \end{aligned}$$ が得られる。

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

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

$$\begin{aligned} 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} \end{aligned}$$

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

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

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

$$\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$ のとき，フィボナッチ数列の漸化式を使うと $$\begin{aligned} F_{m+2}&=F_{m+1}+F_{m}\\ &=F_{m-1}+2F_{m}\\ &=F_{m-1}F_2+F_{m}F_{3} \end{aligned}$$ となり成立。

• $n=k$ と $n=k-1$ の場合も正しいと仮定して $n=k+1$ の場合を計算すると， $$\begin{aligned} 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} \end{aligned}$$ となり成立。

• $n=1$ のとき，$F_2 F_0 - {F_1}^2 = 0-1= (-1)^2$ より成立する。

• $n = k$ で成立すると仮定する。
  この下で $n = k+1$ のときは $$\begin{aligned} &F_{k+2} F_{k} - {F_{k+1}}^2\\ &= (F_{k+1} + F_k) F_k - {F_{k+1}}^2\\ &= {F_k}^2 + F_{k+1} (F_k - F_{k+1})\\ &= {F_k}^2 - F_{k+1} F_{k-1}\\ &= - (F_{k+1} F_{k-1} - {F_k}^2)\\ &= (-1)^{k+1} \end{aligned}$$ より成立する。

よって数学的帰納法より従う。