什么是数学归纳法？

数学归纳法的思想是 有限到无限 的递推逻辑，证明某个命题对其所有定义范围均成立，其本质是：

1. 基例：证明命题在初始条件 $n = base$ 下成立。
2. 归纳假设：假设某个命题在 $n = k$ 的时候成立。
3. 归纳步骤：证明某个命题在 $n = k + 1$ 的时候也成立。

若上述条件均满足则说明命题对 $n \ge base$ 的在定义域内的自然数且均成立。

在某些特殊情况下，如当前状态可能依赖于多个前置状态，在归纳假设时需要假设 $n \le k$ 均成立，此方法被称为强归纳法。

例题

用数归证明斐波那契数列通项公式

命题：斐波那契数列满足 $F(n) = \frac{\phi^n – \psi^n}{\sqrt{5}}$，其中 $\phi = \frac{1+\sqrt{5}}{2}$（黄金比例），$\psi = \frac{1-\sqrt{5}}{2}$。

证明：

1. 基例

   • 当 $n = 0$ 时，$F(0) = 0$，代入上式成立。
   • 当 $n = 1$ 时，$F(1) = 1 $，代入上式成立。

2. 归纳假设

   由于 $F(n)$ 依赖于多个前驱，故需要使用强归纳法。

   • 归纳假设所有 $k \le n$，$F(k) = \frac{\phi^k – \psi^k}{\sqrt{5}}$ 均成立。

3. 归纳步骤

   • 根据递推公式 $F(n + 1) = F(n) + F(n – 1)$ 可得：
     $$
     F(n+1) = \frac{\phi^n – \psi^n}{\sqrt{5}} + \frac{\phi^{n-1} – \psi^{n-1}}{\sqrt{5}} = \frac{\phi^n + \phi^{n-1} – (\psi^n + \psi^{n-1})}{\sqrt{5}}.
     $$

   • 由于 $\phi$ 和 $\psi$ 方程 $x^2 = x + 1$ 的两个解，所以我们可以得到：
     $$
     \phi^{n+1} = \phi^n + \phi^{n-1}, \
     \psi^{n+1} = \psi^n + \psi^{n-1}.
     $$

   • 带入可得：
     $$
     F(n+1) = \frac{\phi^{n+1} – \psi^{n+1}}{\sqrt{5}}.
     $$

   证毕