形式陈述

设命题 $P(n)$$P(n)$ 对自然数 $n\ge n_0$$n\ge n_0$ 定义。若

$$ P(n_0),\qquad \forall n\ge n_0\;(P(n)\Rightarrow P(n+1)), $$$$P(n_0),\mathrm{\forall }n\ge n_0(P(n)\Rightarrow P(n+1)),$$

则 $P(n)$$P(n)$ 对所有 $n\ge n_0$$n\ge n_0$ 成立。它等价于自然数系统的归纳公理。

直觉

基例把证明接到数轴上，归纳步保证一旦到达某处就能前进一步。两者缺一不可，归纳假设只能按当前归纳步规定使用。

例子与边界

可用归纳法证明 $1+\cdots+n=n(n+1)/2$$1+\cdots +n=n(n+1)/2$。若基例从 $n=1$$n=1$ 开始却声称覆盖 $n=0$$n=0$，结论有缺口。错误归纳常在从 $n$$n$ 到 $n+1$$n+1$ 时暗中改变不可保持的条件。

推论与应用

归纳法证明递归算法正确性、有限结构性质和递推公式。强归纳、结构归纳与良基归纳是同一思想的推广。

参考资料

• Richard Hammack, Book of Proof, 3rd ed., 2018, Chapter 10。
• Daniel J. Velleman, How to Prove It: A Structured Approach, 3rd ed., Cambridge University Press, 2019, Mathematical Induction chapter。