奠基 · 递推 · 起点

数学归纳法的两步与它的边界

与 $n$ 有关的命题往往需要对无穷多个 $n$ 验证，逐个代入永远做不完。数学归纳法把这件无穷的工作压成两步：证明命题在起点成立，再证明「若在 $n$ 处成立则在 $n+1$ 处也成立」。两步齐备后，命题沿正整数逐级传递下去。

1 · 两步的分工

定理 1.1（数学归纳法） 设 $P(n)$ 是关于正整数 $n$ 的命题。若 $P(n_0)$ 成立，且对任意 $n \ge n_0$ 由 $P(n)$ 成立可推出 $P(n+1)$ 成立，则 $P(n)$ 对一切 $n \ge n_0$ 成立。

奠基步给出第一块骨牌，递推步保证每一块都能推倒下一块。两步缺一不可，而且缺的方式不同：缺奠基步时递推链条完好但无处启动， $P(n)$ 可以整条都是假的——「 $n = n+1$ 」这个假命题就满足递推步；缺递推步时验证再多项也只是有限多项。

例 1.1 证 $1 + 3 + 5 + \dots + (2n - 1) = n^2$ 。奠基： $n = 1$ 时左端 $1$ 、右端 $1$ ，成立。递推：设 $n$ 处成立，则 $n+1$ 处的左端等于 $n^2 + (2n + 1) = (n+1)^2$ ，即 $n+1$ 处的右端。两步齐备，命题对一切正整数成立。

图 1-1 · 逐行核对命题在各个

n

处成立与否，首个不成立的行被标出。可切换命题并调核对到的项数，观察起点不是 1 的那两条与素数陷阱那一条。

2 · 归纳假设必须用上

递推步的要求是「由 $P(n)$ 推出 $P(n+1)$ 」，若推导过程完全没有用到 $P(n)$ ，那就不是归纳，而是直接证明了 $P(n+1)$ ——这时归纳法本身是多余的，且往往说明推导有漏洞。例 1.1 的递推步里， $n^2$ 这一项正是归纳假设提供的，把左端 $n$ 项之和换成了闭式；不用它就得重新面对求和。

判断一次归纳是否真正用上假设，办法是把假设那一行删掉再读一遍推导。读得通说明用不着归纳法，读不通才是正常的。

3 · 验证有限多项不是证明

$f(n) = n^2 + n + 41$ 在 $n = 0, 1, \dots, 39$ 处的取值全是素数： $41, 43, 47, 53, \dots, 1601$ 。连续四十次验证都通过，命题「 $f(n)$ 恒为素数」看着相当可信。 $n = 40$ 处它失效了： $f(40) = 1681 = 41^2$ 。

这个多项式是欧拉给出的。它的用处不在于产生素数，而在于说明枚举验证的极限：四十项的连中不构成任何证明，而归纳法只要两步。本页的 lab 里这一条与前几条命题并列，唯一的区别是它的核对表在第 $41$ 行（ $n = 40$ ）翻成不成立。

警示 · 反过来也要留神：核对表全绿只说明「在核对到的范围内没有反例」，不说明命题成立。firstMismatch 的返回值是 null 时，正确的读法是「前 $N$ 项内没找到反例」，不是「命题为真」。把它当作证明用，犯的就是本节这条错。

4 · 起点不必是 1

递推步只要求「从某处起每一步都能传下去」，起点 $n_0$ 由命题本身决定。 $2^n > n^2$ 就不是从 $n = 1$ 起成立的： $n = 1$ 时 $2 > 1$ 成立，而 $n = 2$ 时两端都是 $4$ 、 $n = 3$ 时 $8 < 9$ 、 $n = 4$ 时两端都是 $16$ ，三处都不成立； $n = 5$ 时 $32 > 25$ 重新成立，此后一直成立。这条命题的正确表述是「对一切 $n \ge 5$ 成立」，奠基步取 $n_0 = 5$ 。

有趣的是 $n = 1$ 处它也成立，却接不上递推链——递推步在 $n = 1$ 处推不出 $n = 2$ ，孤立的一个真值不构成起点。核对表上这一条会显示成「首行成立、第二至第四行不成立、其后全部成立」，正好说明起点必须选在递推步真正生效的位置。

5 · 参考文献

Mathematical induction. Wikipedia. 归纳法的表述、变体与常见错误。https://en.wikipedia.org/wiki/Mathematical_induction
Formula for primes. Wikipedia. $n^2 + n + 41$ 这类多项式与素数生成的关系。https://en.wikipedia.org/wiki/Formula_for_primes
All horses are the same color. Wikipedia. 归纳步看似成立而实际有漏洞的经典反例。https://en.wikipedia.org/wiki/All_horses_are_the_same_color