数学归纳法

归纳法通过说明已建立的情形怎样支持后续情形，证明一整族命题。它不是检查许多例子后猜测规律会继续。真正的工作是准确选择归纳命题、给足初始情形，并确保归纳步骤使用的结论都有依据。

全文约定 $\mathbb N=\{0,1,2,\ldots\}$。从 $1$ 开始的定理证明的是 $n\ge1$ 的结论，除非另行检查，否则并未证明 $n=0$。普通归纳与强归纳是等价原理，区别在于哪一种假设形式更方便使用 [1][1] Z. Abel, B. Chapman, and E. Demaine, “Lecture 03: Casework and Strong Induction,” 2024. MIT 6.1200J/18.062J, Mathematics for Computer Science; revised February 14, 2024. https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec03.pdf。

把起点写进归纳原理

定理普通归纳原理

固定 $n_0\in\mathbb N$，对每个整数 $n\ge n_0$ 给出命题 $P(n)$。假设：

1. $P(n_0)$ 成立。
2. 对每个整数 $k\ge n_0$，$P(k)$ 蕴涵 $P(k+1)$。

那么对每个整数 $n\ge n_0$，$P(n)$ 都成立。

这里把归纳法作为自然数的一个可用原理。也可以从良序性等其他刻画出发证明某种表述，但必须先建立相应刻画。

归纳步骤本身是条件证明：任取 $k\ge n_0$，暂时假设 $P(k)$，建立 $P(k+1)$。这不是假设存在某个方便的 $k$，也不是先假定所有 $k$ 都满足最终结论。基础情形提供起点，归纳步骤提供此后的每次过渡。

普通归纳：明确指出使用假设的位置

命题前若干个正整数之和

对每个整数 $n\ge1$，

$$\sum_{i=1}^{n}i=\frac{n(n+1)}2.$$

求和记号表示让整数指标从 $1$ 到 $n$，依次把对应项加起来。从 $k$ 项扩展到 $k+1$ 项时，先拆出最后一项，就会出现归纳假设能够处理的那个和。

证明

$n=1$ 时，两边都为 $1$。任取 $k\ge1$，假设

$$\sum_{i=1}^{k}i=\frac{k(k+1)}2.$$

于是

$$\begin{aligned} \sum_{i=1}^{k+1}i &=\sum_{i=1}^{k}i+(k+1)\\ &=\frac{k(k+1)}2+(k+1)\\ &=\frac{(k+1)(k+2)}2. \end{aligned}$$

第二个等号使用了归纳假设，最后一式正是 $n=k+1$ 时需要的公式。由归纳原理，结论对所有整数 $n\ge1$ 成立。

化简之前先写出 $k+1$ 时的目标，能够更容易发现漏加末项或最终指标不对的问题。归纳证明验证的是一个候选公式；发现公式的过程可能需要试算或其他论证。

强归纳：使用真正需要的较小情形

定理强归纳原理

固定 $n_0\in\mathbb N$，先证明 $P(n_0)$。对每个 $k\ge n_0$，假设全部整数 $n_0\le j\le k$ 都满足 $P(j)$，并据此证明 $P(k+1)$。那么所有整数 $n\ge n_0$ 都满足 $P(n)$。

当下一步依赖多个先前指标，或只有分解对象后才知道需要哪个指标时，强归纳很方便。但它能证明的命题并不比普通归纳更多。要从普通归纳得到它，只需对加强后的陈述“所有 $n_0\le j\le n$ 都满足 $P(j)$”使用普通归纳。反过来，强归纳假设当然包含普通归纳需要的前一项。

命题每个至少为二的整数都能写成素数乘积

对每个整数 $n\ge2$，$n$ 都可以写成有限个素数的乘积；单个素数也算只有一个因子的乘积。

证明

$n=2$ 时成立，因为 $2$ 是素数。任取 $k\ge2$，假设从 $2$ 到 $k$ 的全部整数都满足结论，考察 $k+1$。

若 $k+1$ 是素数，直接用单因子表示。若为合数，写成 $k+1=ab$，其中 $2\le a,b<k+1$。强归纳假设同时适用于 $a,b$，所以它们各自能写成素数乘积。把两个表示相乘，就得到 $k+1$ 的素数乘积表示。

由归纳法，结论对每个 $n\ge2$ 成立。

因子不一定等于 $k$，所以能使用所有较小情形很有用。这证明的是素因子分解的存在性，没有证明唯一性；后者是另一个定理。

从递推式判断需要几个基础情形

例依赖前两项的递推

设 $a_0=4$、$a_1=6$，且

$$a_{n+1}=2a_n-a_{n-1}\qquad(n\ge1).$$

前几项提示 $a_n=2n+4$。递推要使用前两项，因此两个初始值都需要检查。

证明

公式在 $n=0$ 和 $n=1$ 时都成立。任取 $k\ge1$，假设从 $0$ 到 $k$ 的每个指标都满足公式，特别地可以使用第 $k$ 和 $k-1$ 项。于是

$$\begin{aligned} a_{k+1}&=2(2k+4)-\bigl(2(k-1)+4\bigr)\\ &=2k+6\\ &=2(k+1)+4. \end{aligned}$$

由包含两个已检查初始情形的强归纳，公式对所有 $n\ge0$ 成立。

也可以把相邻两项的恒等式一起装进归纳命题，再用普通归纳。关键是下一步消耗了哪些先前事实，而不是证明标题写“普通”还是“强”。限制 $k\ge1$ 也确保调用的 $a_{k-1}$ 没有越出数列的定义范围。

先找逻辑缺口，再增加计算

缺口	为什么证明没有完成
只验证基础情形	没有通向更大指标的过渡
只证明归纳蕴涵	一串蕴涵未必有任何为真的起点
归纳步骤假设 $P(k+1)$	把目标当成了尚未证明的前提
只证明 $P(k)\to P(k+2)$	一个起点只能到达其中一个奇偶类
在 $k=0$ 时使用 $P(k-1)$	调用了范围以外的情形
步骤只在额外阈值之后成立	阈值之前的所有指标还需覆盖

例如，令 $P(n)$ 表示“$n$ 是偶数”。$P(0)$ 和 $P(k)\to P(k+2)$ 都成立，却不能证明所有自然数都是偶数。问题出在没有覆盖全部可达指标，而不是计算不够复杂。

归纳法也能证明不等式、整除性质和递归对象的性质，但对象必须沿适当的良基结构缩小。这里的自然数原理不能自动变成关于任意实数的证明。对算法而言，正确性与终止性也可能需要分开论证，即使二者都使用归纳法。

练习：普通归纳与计数

练习前若干个奇数之和

对每个 $n\in\mathbb N$，证明

$$\sum_{i=1}^{n}(2i-1)=n^2.$$

约定 $n=0$ 时空和为零，并判断普通归纳是否足够。

查看解析

解

$n=0$ 时两边为零。任取 $k\ge0$，假设公式在 $k$ 时成立。新增项为 $2(k+1)-1=2k+1$，所以

$$\sum_{i=1}^{k+1}(2i-1)=k^2+(2k+1)=(k+1)^2.$$

只使用了前一个和，普通归纳已足够。$k+1$ 项的末项是 $2k+1$，不是 $2k+3$。

练习平方和与棋盘计数

对整数 $n\ge1$，证明

$$\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}6.$$

再用它计算 $n\times n$ 棋盘中所有边沿网格线的正方形数量。

查看解析

解

$n=1$ 时结果为 $1$。任取 $k\ge1$，假设公式成立，加入下一项的平方：

$$\begin{aligned} \sum_{i=1}^{k+1}i^2 &=\frac{k(k+1)(2k+1)}6+(k+1)^2\\ &=\frac{(k+1)(2k^2+7k+6)}6\\ &=\frac{(k+1)(k+2)(2k+3)}6. \end{aligned}$$

这就是 $k+1$ 时的公式。棋盘上边长为 $s$ 个格子的正方形有 $(n-s+1)^2$ 个位置，因此总数为

$$\sum_{s=1}^{n}(n-s+1)^2=\sum_{i=1}^{n}i^2.$$

$8\times8$ 棋盘得到 $8\cdot9\cdot17/6=204$。明确“边沿网格线”这一条件，才能确定到底数的是哪些正方形。

练习奇数的平方和

对 $n\in\mathbb N$，证明

$$\sum_{i=1}^{n}(2i-1)^2=\frac{n(2n-1)(2n+1)}3.$$

查看解析

解

$n=0$ 时两边为零。若任意 $k\ge0$ 时公式成立，加入 $(2k+1)^2$ 后有

$$\begin{aligned} \frac{k(2k-1)(2k+1)}3+(2k+1)^2 &=\frac{(2k+1)(2k^2+5k+3)}3\\ &=\frac{(k+1)(2k+1)(2k+3)}3. \end{aligned}$$

结果与 $k+1$ 时的公式一致，归纳完成。

练习不等式也可以归纳

对每个 $n\in\mathbb N$，证明 $2^n\ge n+1$。

查看解析

解

$n=0$ 时两边均为 $1$。设 $2^k\ge k+1$，其中 $k\ge0$。乘上正数 $2$ 不改变不等号方向，所以

$$2^{k+1}\ge2(k+1)\ge k+2.$$

第二个不等号使用 $k\ge0$，最后一项正是 $k+1$ 时的目标，因此可以应用归纳原理。

练习：固定参数并检查指标

练习可以归纳，也可以裂项

对 $n\ge1$，证明

$$\sum_{i=1}^{n}\frac1{(2i-1)(2i+1)}=\frac{n}{2n+1}.$$

查看解析

解

基础情形两边为 $1/3$。下一步使用假设并通分：

$$\begin{aligned} \frac{k}{2k+1}+\frac1{(2k+1)(2k+3)} &=\frac{2k^2+3k+1}{(2k+1)(2k+3)}\\ &=\frac{k+1}{2k+3}. \end{aligned}$$

结果正是 $k+1$ 时的目标。另一种方法是先写成

$$\frac1{(2i-1)(2i+1)} =\frac12\left(\frac1{2i-1}-\frac1{2i+1}\right),$$

再让有限和中的中间项相消。两种方法用不同组织方式证明同一恒等式。

练习归纳时固定另一个参数

固定整数 $q\ge0$，对所有整数 $n\ge1$ 证明

$$\sum_{j=1}^{n}j(j+1)\cdots(j+q) =\frac{n(n+1)\cdots(n+q+1)}{q+2}.$$

$q=0$ 时，被加项就是 $j$。

查看解析

解

对 $n$ 归纳时，始终固定 $q$。$n=1$ 时，右边约去 $q+2$ 后得到 $1\cdot2\cdots(q+1)$，与左边相同。若公式在 $k$ 时成立，新增一项后提取公因子：

$$\begin{aligned} &\frac{k(k+1)\cdots(k+q+1)}{q+2} +(k+1)\cdots(k+q+1)\\ &\qquad=(k+1)\cdots(k+q+1) \left(\frac{k}{q+2}+1\right)\\ &\qquad=\frac{(k+1)\cdots(k+q+2)}{q+2}. \end{aligned}$$

$q\ge0$ 保证分母非零，最后一式就是 $k+1$ 时的目标。又因为最初固定的 $q$ 任意，结论适用于全部允许参数。

练习带权等比和

固定实数 $r\ne1$，对全部 $n\in\mathbb N$ 证明

$$\sum_{j=0}^{n}(j+1)r^j =\frac{[(r-1)n+(r-2)]r^{n+1}+1}{(r-1)^2}.$$

常数项为 $1$，$r=0$ 时也如此。给出 $r=2$、$r=3$ 的特例，再单独处理 $r=1$。

查看解析

解

$n=0$ 时，右边分子为 $(r-2)r+1=(r-1)^2$，结果为 $1$。记 $A_k=(r-1)k+(r-2)$，展开可得系数恒等式

$$A_{k+1}r-A_k=(k+2)(r-1)^2.$$

记左边的和为 $S_n$。任取 $k\ge0$，归纳假设给出

$$S_k=\frac{A_k r^{k+1}+1}{(r-1)^2}.$$

新增项为 $(k+2)r^{k+1}$。代入 $S_k$ 的表示，并使用上述系数恒等式，得到

$$\begin{aligned} S_{k+1}&=S_k+(k+2)r^{k+1}\\ &=\frac{A_{k+1}r^{k+2}+1}{(r-1)^2}. \end{aligned}$$

这就是 $k+1$ 时的公式。特别地，

$$\sum_{j=0}^{n}(j+1)2^j=n2^{n+1}+1,$$$$\sum_{j=0}^{n}(j+1)3^j=\frac{(2n+1)3^{n+1}+1}{4}.$$

$r=1$ 时直接使用整数求和公式，得到 $(n+1)(n+2)/2$；不能代入上面的商式，否则会除以零。这里也修正了一处常见指标错误：新加一项的系数是 $k+2$，不是 $k+1$。

从证明继续看结构

每次归纳都要说明指标范围、基础情形，以及步骤调用了哪些更早的实例。数系、算法与递归会把这些依赖与递归定义连接起来；集合、函数、序列与求和则继续发展例子中使用的记号。

参考文献

1. [1] Z. Abel, B. Chapman, and E. Demaine, “Lecture 03: Casework and Strong Induction,” 2024. MIT 6.1200J/18.062J, Mathematics for Computer Science; revised February 14, 2024. https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec03.pdf ↩