数学归纳法

引入

要证明”对所有自然数 $n$ ， $1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$ “，逐个验证是不可能的——自然数有无穷多个。

为什么”验证 $n = 1$ 成立”和”假设 $n = k$ 成立能推出 $n = k + 1$ 成立”这两步，就能覆盖全部自然数？

多米诺骨牌为什么会全部倒下？它需要满足什么条件？

定义

数学归纳法是一种证明与自然数有关的命题的方法。若要证明命题 $P (n)$ 对所有 $n \geq n_{0}$ 成立，只需证明：

奠基： $P (n_{0})$ 成立；

递推：若 $P (k)$ 成立（ $k \geq n_{0}$ ），则 $P (k + 1)$ 成立。

把命题 $P (n)$ 想成一排多米诺骨牌：

步骤	对应	作用
奠基	推倒第一块	保证有起点
递推	每块倒下都能带倒下一块	保证传递

两者缺一不可。只有奠基没有递推，只能证明第一块倒下；只有递推没有奠基，整排骨牌可能一块也不倒。

这不是”验证了很多情况所以成立”，而是”证明了传递机制存在”。所以归纳法能覆盖无穷多个 $n$ ，而枚举不能。

以 $1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$ 为例：

步骤	内容
奠基	$n = 1$ 时，左边 $= 1$ ，右边 $= \frac{1 \cdot 2}{2} = 1$ ，成立
假设	设 $n = k$ 时成立，即 $1 + 2 + \dots + k = \frac{k ( k + 1 )}{2}$
递推	当 $n = k + 1$ 时， $1 + 2 + \dots + k + (k + 1) = \frac{k ( k + 1 )}{2} + (k + 1) = \frac{( k + 1 ) ( k + 2 )}{2}$ ，也成立
结论	由归纳法，对一切 $n \in N^{*}$ 成立

递推步骤中必须”用上假设”。如果推导 $n = k + 1$ 时没有用到 $P (k)$ ，那这个证明其实与归纳法无关，只是对任意 $k$ 的直接证明。

类型	假设的内容	适用
第一归纳法	只假设 $P (k)$	递推只依赖前一项
第二归纳法	假设 $P (n_{0}), P (n_{0} + 1), \dots, P (k)$ 全部成立	递推依赖前若干项

第二归纳法适合” $P (k + 1)$ 依赖前面多个结论”的情形，例如证明每个大于 $1$ 的整数都能分解为素数乘积（需要用到更小的因子）。

两者在逻辑上等价：第二归纳法可以用第一归纳法证明其合法性。

跨步归纳要特别注意：若每次跨 $2$ 步，必须验证两个起点，否则只能覆盖与起点同奇偶的 $n$ 。

归纳法不能”发现”结论，只能”验证”结论。公式往往要先猜出来（通过计算前几项），再用归纳法证明。

第二归纳法为什么与第一归纳法等价？

归纳法能否用于证明实数上的命题？

如果命题对无穷多个 $n$ 成立，能否反推它对所有 $n$ 成立？