什么是数学归纳法？
数学归纳法的思想是 有限到无限 的递推逻辑，证明某个命题对其所有定义范围均成立，其本质是：
基例：证明命题在初始条件 $n = base$ 下成立。
归纳假设：假设某个命题在 $n = k$ 的时候成立。
归纳步骤：证明某个命题在 $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}$。
证明：
基例
当 $n = 0$ 时，$F(0) = 0$，代入上式成立。
当 $n = 1$ 时，$F(1) = 1 $，代入上式成立。
归纳假设
由于 $F(n)$ 依赖于多个前驱，故需要使用强归纳法。
归纳假设所有 $k \le n$，$F(k) = \frac{\phi^k – \psi^k}{\sqrt{5}}$ 均成立。
归纳步骤
根据递推公式 $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}}.
$$
证毕