数学归纳法

数学归纳法（mathematical induction）用来证明从某个整数开始的一整串命题。它需要两件事：起点成立；任取一个已经成立的位置，下一位置也成立。只核对前十项，不能代替第二件事。

例如把第 $n$ 个奇数以前的所有正奇数相加： $$1+3+5+\cdots +(2n-1)=n^2(n\ge 1).$$ 前几次计算是 $1=1^2$、$1+3=2^2$、$1+3+5=3^2$。这些数字提示了规律，却没有覆盖任意大的 $n$。要完成证明，需要找出从 $n=k$ 到 $n=k+1$ 时新增的量。

起点与传递步骤

设 $P(n)$ 表示上面的等式，定义域是正整数。起始步：$n=1$ 时，等式两边都是 1。

归纳步：任取正整数 $k$，暂时假定 $P(k)$ 成立，即前 $k$ 个奇数之和为 $k^2$。下一项是 $2(k+1)-1=2k+1$，故 $$\begin{array}{cc}1+3+\cdots +(2k-1)+(2k+1)& =k^2+(2k+1)\\ & =(k+1{)}^2.\end{array}$$ 这正是 $P(k+1)$。归纳步没有把待证结论预先假定为真；它证明的是对任意 $k\ge 1$ 都有效的条件关系 $P(k)\Rightarrow P(k+1)$。起始步给出第一环，传递步骤便把它送到每一个后继整数。

第 k 层正方形增加一行和一列，但交角只数一次，新增 2k+1 个格子。

图中从边长 $k$ 的正方形扩到边长 $k+1$：新的一行有 $k+1$ 格，新的一列除去重复的角还有 $k$ 格，总共 $2k+1$ 格。图解释了归纳式里的增量；对所有 $k$ 的代数等式才使证明完整。

起点不能省略

“若 $n\ge 1$，则 $n+1\ge 1$”无论取多大的 $n$ 都成立，但它不能推出 0 也满足 $n\ge 1$。若命题声称“所有非负整数都大于等于 1”，归纳步虽然成立，起始步 $P(0)$ 却是假的。

起点也可能不在 0 或 1。要证明 $2^n\ge n+1$ 对 $n\ge 0$ 成立，起点是 $2^0=1=0+1$。若已知 $2^k\ge k+1$，则 $2^{k+1}\ge 2(k+1)\ge k+2$（最后一步用到 $k\ge 0$）。写清开始范围，才能检查这些不等式是否真的适用。

强归纳法

有时要证明第 $k+1$ 项，需要用到前面不止一项。强归纳法允许暂时假定从起点到 $k$ 的全部命题都成立，再证明 $P(k+1)$。这并没有加强结论，只是把归纳假设写成适合当前问题的形式。

以素数分解的存在性为例。要证每个 $n\ge 2$ 都能分解成素数的乘积。起点 2 本身是素数。设 2 到 $k$ 都能分解。若 $k+1$ 是素数，已经完成；若是合数，写成 $k+1=ab$，其中 $2\le a,b\le k$。归纳假设分别给出 $a$、$b$ 的素数分解，合在一起便得到 $k+1$ 的分解。这里只证明存在；分解的唯一还要用欧几里得引理。

强归纳与普通归纳等价。若把“从起点到 $n$ 的每个 $P(j)$ 都成立”整体记为 $Q(n)$，强归纳中一次使用多个较早结论，就变成从 $Q(k)$ 推出 $Q(k+1)$ 的普通归纳。选择哪种写法取决于一步证明实际要调用多少项。

与最小反例的关系

假设起始步和归纳步都已证明，却仍有一个不成立的指标。按整数的良序性质，这些反例中有最小的 $m$。它不能是起点；前一个指标 $m-1$ 没有失败，归纳步就迫使 $P(m)$ 成立，矛盾。这说明归纳法的力量来自整数没有“跳过前一项”的最小反例。

试着把奇数和改成前 $n$ 个偶数之和。新增项为 $2(k+1)$；若猜和为 $n(n+1)$，归纳步给出 $k(k+1)+2(k+1)=(k+1)(k+2)$，且 $n=1$ 时两边都为 2。这样，猜测、起点和传递步骤分别得到了检验。

参考资料

• ProofWiki，Mathematical Induction：归纳原则及起点、归纳假设的区分。
• Oscar Levin，Discrete Mathematics: An Open Introduction，§2.5：有限归纳与算例。
• 继续阅读：逻辑、皮亚诺公理、素数。