使用数学归纳法证明斐波那契数列通项公式()

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

定义

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

\(\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 = 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_{n} = F_{n-2} + F_{n-1}\)，也就是说

我们要证明 \(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}}\) 化简成前面的形式。那么我们开始计算，看看是否可行：

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

把这两个式子代入上式，

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

因此得证。

2023 年 5 月 1 日

————————

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

定义

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

\(\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 = 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_{n} = F_{n-2} + F_{n-1}\)，也就是说

我们要证明 \(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}}\) 化简成前面的形式。那么我们开始计算，看看是否可行：

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

把这两个式子代入上式，

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

因此得证。

2023 年 5 月 1 日