使用数学归纳法证明斐波那契数列通项公式：\(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 日
标签：phi,dfrac,sqrt,证明,斐波,通项,公式,那契,hat From： https://www.cnblogs.com/dengstar/p/17366490.html