ビネーの公式の導出（数学的帰納法）
ビネーの公式
フィボナッチ数列 $\{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_{n+2} = F_{n+1} + F_n$, $F_1=F_2=1$ からビネーの公式を数学的帰納法で導いてみよう。
$\alpha = \frac{1 + \sqrt{5}}{2}$ と $\beta = \frac{1 - \sqrt{5}}{2}$ とする。$\alpha^2 = \alpha+1$ かつ $\beta^2 = \beta + 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}$
例題. $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\}$$ は正しい.
