ビネーの公式の導出（数学的帰納法）

フィボナッチ数列の一般項が次の式で表されることを, 数学的帰納法を用いて証明する。 $$ F_n = \frac{1}{\sqrt{5}} ( \alpha^n - \beta^n ) \quad \cdots (\text{＊}) $$ ただし, $\alpha = \frac{1+\sqrt{5}}{2}, \beta = \frac{1-\sqrt{5}}{2}$ とする。これらは $x^2 - x - 1 = 0$ の解であり, $\alpha^2 = \alpha+1, \beta^2 = \beta+1$ を満たす。

$n=1$ のとき：右辺 $= \frac{1}{\sqrt{5}}(\alpha - \beta) = \frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2} - \frac{1-\sqrt{5}}{2} \right) = 1 = F_1$
$n=2$ のとき：右辺 $= \frac{1}{\sqrt{5}}(\alpha^2 - \beta^2) = \frac{1}{\sqrt{5}}\{(\alpha+1) - (\beta+1)\} = \frac{\alpha-\beta}{\sqrt{5}} = 1 = F_2$
よって, $n=1, 2$ のとき等式(＊)は成り立つ。

$n \leqq k$ ($k \geqq 2$) のすべての自然数 $n$ について等式(＊)が成り立つと仮定する。 このとき, $n=k$ および $n=k-1$ において $$ F_k = \frac{1}{\sqrt{5}}(\alpha^k - \beta^k), \quad F_{k-1} = \frac{1}{\sqrt{5}}(\alpha^{k-1} - \beta^{k-1}) $$ が成り立つ。

漸化式 $F_{k+1} = F_k + F_{k-1}$ より $$ \begin{aligned} F_{k+1} &= \frac{1}{\sqrt{5}}(\alpha^k - \beta^k) + \frac{1}{\sqrt{5}}(\alpha^{k-1} - \beta^{k-1}) \\ &= \frac{1}{\sqrt{5}} \{ (\alpha^k + \alpha^{k-1}) - (\beta^k + \beta^{k-1}) \} \\ &= \frac{1}{\sqrt{5}} \{ \alpha^{k-1}(\alpha + 1) - \beta^{k-1}(\beta + 1) \} \\ &= \frac{1}{\sqrt{5}} \{ \alpha^{k-1} \cdot \alpha^2 - \beta^{k-1} \cdot \beta^2 \} \\ &= \frac{1}{\sqrt{5}} ( \alpha^{k+1} - \beta^{k+1} ) \end{aligned} $$ となり, $n=k+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\} $$ が成り立つ。