ビネーの公式の導出（数学的帰納法）
フィボナッチ数列の漸化式 $F_{n+2} = F_{n+1} + F_n$, $F_1=F_2=1$ からビネーの公式を数学的帰納法で導いてみよう。
ビネーの公式
フィボナッチ数列 $\{F_n\}$ について,
$$F_n = \frac{1}{\sqrt{5}} \left\{ \left(\frac{1+\sqrt{5}}{2} \right)^n - \left(\frac{1-\sqrt{5}}{2} \right)^n \right\}$$
例題. $F_1=F_2=1$, $n\geqq 3$ のとき $F_{n} = F_{n-1} + F_{n-2}$ という漸化式で定義される数列 $\{ F_n \}$ の一般項を数学的帰納法で導きなさい。
次の式を予測し, すべての自然数 $n$ に対して正しいことを数学的帰納法によって示す.
$$\displaystyle F_n = \frac{1}{\sqrt{5}} ( \alpha^n - \beta^n ).$$
ただし, $\alpha = \frac{1+\sqrt{5}}{2}$ と $\beta = \frac{1-\sqrt{5}}{2}$ とする.
$n=1$ のとき, 左辺は $F_1=1$, 右辺は $\frac{1}{\sqrt{5}} ( \alpha - \beta ) = 1$ で式は成り立つ.
$n=2$ のとき, 左辺は $F_2=1$, 右辺は $\frac{1}{\sqrt{5}} ( \alpha^2 - \beta^2 ) = 1$ で式は成り立つ.
$n=3$ のとき, 左辺は $F_3=2$, 右辺は $\frac{1}{\sqrt{5}} ( \alpha^3 - \beta^3 ) = 2$ で式は成り立つ.
以上により, $n=1, \ 2, \ 3$ のとき, 予想の式は正しい.
$n \geqq 3$ とする. $k \leqq n$ の全ての自然数 $k$ で予想の式が正しいと仮定して, $n+1$ のときも式が正しいかを確かめる.
$$\begin{aligned}
F_{n+1} &= F_n + F_{n-1} \\
&= \frac{1}{\sqrt{5}}(\alpha^{n}- \beta^{n}) + \frac{1}{\sqrt{5}}(\alpha^{n-1}- \beta^{n-1}) \\
&= \frac{1}{\sqrt{5}}\{ (\alpha^n + \alpha^{n-1}) - (\beta^n + \beta^{n-1} ) \} \\
&= \frac{1}{\sqrt{5}}\{ (\alpha +1) \alpha^{n-1} - (\beta +1) \beta^{n-1} \} \\
&= \frac{1}{\sqrt{5}}\{ \alpha^2 \cdot \alpha^{n-1} - \beta^2 \cdot \beta^{n-1} \} \\
&= \frac{1}{\sqrt{5}}\{ \alpha^{n+1} - \beta^{n+1} \}
. \end{aligned}$$
$\alpha^2 = \alpha+1$ かつ $\beta^2 = \beta + 1$ を満たす.
したがって, $n+1$ のときも予想の式が正しいと示された.
ゆえに, 数学的帰納法により, すべての自然数 $n$ に対して $$F_n = \frac{1}{\sqrt{5}} \left\{ \left(\frac{1+\sqrt{5}}{2} \right)^n - \left(\frac{1-\sqrt{5}}{2} \right)^n \right\}$$ は正しい.
e.g. 証明のポイント
$\alpha = \frac{1 + \sqrt{5}}{2}$ は $\alpha^2 = \alpha+1$ を満たす。
$\beta = \frac{1 - \sqrt{5}}{2}$ も $\beta^2 = \beta + 1$ を満たす。
$n=5$ のときの式を, $n=4, 3$ のときの式から作ります。
$F_{5} = F_4 + F_3$
① $F_4=\frac{1}{\sqrt{5}}(\alpha^4- \beta^4)$
② $F_3=\frac{1}{\sqrt{5}}(\alpha^3- \beta^3)$
①+②をします。
$\alpha$ のところは,
$\frac{1}{\sqrt{5}} (\alpha^4 + \alpha^3)$ $= \frac{1}{\sqrt{5}} (\alpha + 1)\alpha^3$ $= \frac{1}{\sqrt{5}} \alpha^2 \cdot \alpha^3$ $= \frac{1}{\sqrt{5}} \alpha^5$
になる。
同様に, $\beta$ のところも,
$-\frac{1}{\sqrt{5}} \beta^5$
になる。
だから,
$F_5 = \frac{1}{\sqrt{5}}(\alpha^5- \beta^5)$
ができる。
