使用数学归纳法证明斐波那契数列通项公式：\(F_{n} = \dfrac{\phi^{n} - \hat{\phi}^{n}}{\sqrt{5}}\)

定义

已知斐波那契数列 \(F\) 定义为：

\[F_{n} = \begin{cases} 0, n = 0\\ n, n = 1\\ F_{n-1} + F_{n-2}, i \ge 2 \end{cases} \]

\(\phi\) 和 \(\hat{\phi}\) 分别为方程 \(x^2 + x + 1 = 0\) 的两个解，且 \(\phi > \hat{\phi}\)。具体而言，\(\phi = \dfrac{1 + \sqrt{5}}{2}\)，\(\hat{\phi} = \dfrac{1 - \sqrt{5}}{2}\)。

证明：\(F_{n} = \dfrac{\phi^{n} - \hat{\phi}^{n}}{\sqrt{5}}\)。

证明

使用数学归纳法进行证明。

思路如下：先通过代入证明该公式当 \(n = 0\) 和 \(n = 1\) 时成立。再证明，若该公式当 \(n = k - 2\) 和 \(n = k - 1\) 时成立，则当 \(n = k\) 时也成立。

如此，因为 \(i = 0\) 和 \(i = 1\) 时成立，可推出 \(i = 2\) 时该公式也成立；因为 \(i = 1\) 和 \(i = 2\) 时成立，可推出 \(i = 3\) 时该公式也成立，以此类推，就可以证明该公式对于所有自然数都成立。

根据以上思路，首先先证明该公式当 \(n = 0\) 和 \(n = 1\) 时成立。这一步可以通过简单的直接代入证明，如下：

\[F_0 = \dfrac{\phi^{0} - \hat{\phi}^{0}}{\sqrt{5}} = \dfrac{1 - 1}{\sqrt{5}} = 0 \\ F_1 = \dfrac{\phi^{1} - \hat{\phi}^{1}}{\sqrt{5}} = \dfrac{1 + \sqrt{5} - (1 - \sqrt{5})}{2} \times \dfrac{1}{\sqrt{5}} = \dfrac{2\sqrt{5}}{2\sqrt{5}} = 1 \]

因为我们已知 \(F_0 = 0\)，\(F_1 = 1\)，所以该公式对于 \(n = 0\) 和 \(n = 1\) 时是成立的。

下面，我们要证明，若该公式当 \(n = k - 2\) 和 \(n = k - 1\) 时成立，则当 \(n = k\) 时也成立。这也正是难点所在（不过事实上，也并没有特别难）。

因为该公式当 \(n = k - 2\) 和 \(n = k - 1\) 时成立，所以我们可以表示出 \(F_{k-2}\) 和 \(F_{k-1}\) 的值：

\[F_{k-2} = \dfrac{\phi^{k-2} - \hat{\phi}^{k-2}}{\sqrt{5}}, F_{k-1} = \dfrac{\phi^{k-1} - \hat{\phi}^{k-1}}{\sqrt{5}} \]

根据斐波那契数列的定义，我们知道 \(F_{n} = F_{n-2} + F_{n-1}\)，也就是说

\[F_{k} = \dfrac{\phi^{k-2} - \hat{\phi}^{k-2}}{\sqrt{5}}+ \dfrac{\phi^{k-1} - \hat{\phi}^{k-1}}{\sqrt{5}} \]

我们要证明 \(F_{n} = \dfrac{\phi^{n} - \hat{\phi^{n}}}{\sqrt{5}}\)，也就是要把上面这个和式 \(\dfrac{\phi^{k-2} - \hat{\phi}^{k-2}}{\sqrt{5}}+ \dfrac{\phi^{k-1} - \hat{\phi}^{k-1}}{\sqrt{5}}\) 化简成前面的形式。那么我们开始计算，看看是否可行：

\[\begin{aligned} F_{k} & = \dfrac{\phi^{k-2} - \hat{\phi}^{k-2}}{\sqrt{5}}+ \dfrac{\phi^{k-1} - \hat{\phi}^{k-1}}{\sqrt{5}} \\ & = \dfrac{\phi^{k-2} - \hat{\phi}^{k-2} + \phi^{k-1} - \hat{\phi}^{k-1}}{\sqrt{5}} \\ & = \dfrac{\phi^{k-2}(1 + \phi) + \hat{\phi}^{k-2}(1 + \hat{\phi})}{\sqrt{5}} \qquad \text{提出公因式} \end{aligned} \]

到这里似乎有点不太找得到头绪，不过我们可以从 \(\phi\) 和 \(\hat{\phi}\) 两个数本身的性质入手。我们知道它们是方程 \(x^2 + x + 1 = 0\) 的两个解，所以一下两个式子是成立的：

\[\phi + 1 = \phi^2 \\ \hat{\phi} + 1 = \hat{\phi} ^ 2 \]

把这两个式子代入上式，

\[\begin{aligned} F_{k} & = \dfrac{\phi^{k-2}(1 + \phi) + \hat{\phi}^{k-2}(1 + \hat{\phi})}{\sqrt{5}} \\ & = \dfrac{\phi^{k-2} \times \phi^2 + \hat{\phi}^{k-2} \times \hat{\phi}^{2}}{\sqrt{5}} \\ & = \dfrac{\phi^{k} - \hat{\phi}^k}{\sqrt{5}} \end{aligned} \]

即 \(F_{n} = \dfrac{\phi^{n} - \hat{\phi^{n}}}{\sqrt{5}}\)

因此得证。

\[Q.E.D \]

2023 年 5 月 1 日