数学归纳法

定义

数学归纳法只用两次验证，便证明性质 $P(n)$P(n) 对自某个下标 $n_0$n0​ 起的一切整数成立：

这两点确立了无穷多个命题。其力量正在于此：所验证的始终只是一个情形与一个蕴涵。

一个比喻，及其界限

一列多米诺骨牌：推倒第一枚，并保证每一枚都推倒下一枚，就足以让它们全部倒下。

比喻在机制上是对的，在范围上是错的。骨牌列是有限的，倒下需要时间；归纳法关涉无穷多个下标，并不在时间中展开。它并非叙述一次传播，而是证明一条性质。

一个走到底的例子

试证前 $n$n 个整数之和等于 $\dfrac{n(n+1)}{2}$2n(n+1)​。

基础情形。 当 $n = 1$n=1：和为 1，而 $\dfrac{1 \times 2}{2} = 1$21×2​=1。

归纳步骤。 设公式在下标 $n$n 处成立。于是：

$1 + 2 + \dots + n + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$1+2+⋯+n+(n+1)=2n(n+1)​+(n+1)=2n(n+1)+2(n+1)​=2(n+1)(n+2)​

这正是下标 $n+1$n+1 处的公式。两步皆成立，故该性质对一切 $n \geq 1$n≥1 成立。

两步缺一不可

只有归纳步骤什么也证明不了。取 $P(n)$P(n) 为「$n = n + 1$n=n+1」。

这条性质是可遗传的：若 $n = n+1$n=n+1，两边各加 1 得 $n + 1 = n + 2$n+1=n+2。这一步传递得完美无缺——而该性质对每个整数都为假，因为没有任何下标能启动它。

只有基础情形同样不够：一条性质可以在 1 处为真，其后为假。

强归纳法

某些证明所需不止前一个下标。强归纳法假设对一切 $k \leq n$k≤n 都有 $P(k)$P(k)，而非仅对 $n$n。

当归纳步骤须回溯到更早的下标时，它就派上用场——例如把整数分解为素因子，所引用的是任意两个更小的因子，而非前一个数。

小结

一个起点与一个会传递的步骤便证明了无穷多个情形；二者皆不可省。