数学归纳法 I：公式、整除与不等式

上一章我们练习了逆否和反证：先绕到一个更好下手的方向，再把结论逼出来。数学归纳法处理的是另一类麻烦——题目想一次证明无穷多个命题。

比如下面这个等式：

把 $n=1$、$2$、$3$ 代进去都不难。可题目说的是“对所有正整数 $n$”，所以检查一百个值也不够。第 $101$ 个值或更远的某个值，仍然可能出问题。

归纳法的办法是把这些命题排成一条链：先让链条的第一环成立，再证明任何一环只要成立，就能带动下一环。它不是替我们猜公式，也不只是批量计算；它是在证明一条覆盖所有目标整数的传递规则。

归纳证明的主线：起点成立；任取一格，假设它成立并推出下一格；于是从起点开始的全部整数都被覆盖。

把一个结论拆成一族命题

归纳法中的 $P(n)$ 是一个带整数参数的命题。每给 $n$ 一个具体值，就得到一个可以判断真假的命题。

例如，定义

那么 $P(1)$、$P(2)$ 和 $P(3)$ 分别是

这里有一个很实用的写作习惯：正式证明前，先把 $P(n)$ 完整写出来。否则“假设它成立”“推出下一步”里的“它”和“下一步”很容易失去对象，尤其当题目同时出现 $n$、$m$、$r$ 等多个字母时。

先确定范围，再确定起点

命题的范围是归纳证明的一部分，不是句末随手补上的条件。下面三句话的起点分别是 $0$、$1$ 和 $4$：

如果结论只对 $n\ge4$ 成立，就应该从 $P(4)$ 开始。硬从 $P(1)$ 开始，既没有必要，也可能根本做不到。

本章统一把起点记作 $n_0$。要证明的完整命题是

只写“对所有 $n$”通常太宽。比如 $2^n\ge n^2$ 在 $n=3$ 时是假的，却从 $n=4$ 开始一直成立。边界写错，整个定理就变了。

检查很多个值为什么还不算证明

列出前几个值有两个作用：帮助发现模式，也帮助抓住明显错误。它不能覆盖无穷多个值。

假设我们检查了 $P(1)$ 到 $P(1000)$。这只得到一个有限合取：

它没有说明 $P(1001)$，更没有说明任意遥远的 $P(n)$。归纳步骤提供的正是缺失的统一规则：它不是再检查一个值，而是对任意符合范围的 $k$ 证明一个条件命题。

普通归纳法的逻辑骨架

要证明从 $n_0$ 开始的所有 $P(n)$，需要两项事实：

以及

有了这两项，就能推出

把它展开，链条更容易看清：

从基础得到 $P(n_0)$，用第一条蕴含得到 $P(n_0+1)$，再用下一条得到 $P(n_0+2)$。任意目标 与起点之间只隔有限步，因此总能沿链条走到它。

多米诺只是直觉模型。真正起作用的是起点 $P(n_0)$ 与对每个 $k\ge n_0$ 都有效的蕴含 $P(k)\Rightarrow P(k+1)$。

基础、假设、步进和结论各做什么

为什么“假设 $P(k)$”不是循环论证

第一次接触归纳法，最合理的疑问就是：结论还没证明，为什么可以先假设 $P(k)$？

关键在于，我们没有无条件地宣布 $P(k)$ 为真。归纳步骤要证明的是一个蕴含：

证明蕴含时，本来就可以临时假设前件成立，再推出后件。上一章证明“若一个整数的平方是偶数，则这个整数是偶数”时，也会先假设“平方是偶数”。那不是把最终结论当作已知，而是在研究：一旦前件成立，后件是否必然跟上。

归纳假设与循环论证有三处明确区别：

1. 假设的是 $P(k)$，目标是 $P(k+1)$，两者不是同一个命题。
2. $k$ 是任取的，推导必须对每个 $k\ge n_0$ 都有效，不能挑一个方便的 。

真正的循环写法是：

它没有建立从上一格到下一格的桥。归纳法允许你站在 $P(k)$ 上造桥，但不允许你先站到桥的另一端。

从题目到证明：先写四行草稿

很多归纳证明不是算不动，而是目标没写准。正式变形前，建议先写下面四行：

例如，对于

归纳假设是

目标不是在原式末尾机械地写一个 $k+1$，而是把整个命题中的 $n$ 换成 $k+1$：

也就是

这一步常常直接暴露解题方向：左边比 $P(k)$ 多了最后一项 $2k+1$，所以应当从归纳假设左边加上 $2k+1$ 开始。

归纳步骤只负责一阶的落差。困难通常不在“跳得远”，而在找准 $P(k)$ 与 $P(k+1)$ 的差别。

一份可以直接使用的证明模板

模板不是为了把证明写得千篇一律。它的作用是守住逻辑边界。真正需要思考的地方仍然是：$P(k+1)$ 比 $P(k)$ 多了什么，怎样把新增部分接上旧结论。

求和公式：拆出新增的最后一项

求和题的归纳步骤有一个稳定动作：把前 $k+1$ 项拆成“前 $k$ 项”和“第 $k+1$ 项”。前一块由归纳假设处理，后一块负责把右侧公式推进一格。

从 $P(k)$ 到 $P(k+1)$ 的核心动作：保留已知的前 $k$ 项，再补上新出现的最后一项。

例题：前 $n$ 个正整数之和

证明对所有正整数 $n$，

正式写之前先看一步的差别。$P(k+1)$ 的左边比 $P(k)$ 多 $k+1$，右边应从

变成

所以路线很直接：给归纳假设两边加上 $k+1$，再整理。

例题：前 $n$ 个奇数之和

证明对所有正整数 $n$，

这个例子很短，却展示了归纳证明里最有用的“对差”思路：旧结果是 $k^2$，新结果是 $(k+1)^2$，两者相差

而 $2k+1$ 恰好是和式新增的那一项。

例题：平方和公式

公式往往先由小规模计算或别的方法猜出，再交给归纳法验明正身。现在证明对所有正整数 $n$，

这里最容易出现的失误，是整理出一个复杂多项式后就停下。归纳步骤的终点必须与 $P(k+1)$ 的目标式逐项对上：三个因子应是 $k+1$、$k+2$ 和 $2k+3$。

整除命题：把“整除”翻译成整数倍

若 $a$ 和 $b$ 是整数，$a\mid b$ 的定义是：存在整数 $q$，使得

因此“$a$ 整除某个表达式”的归纳假设，最好立即翻译成“这个表达式等于 $a$ 乘某个整数”。只写“由归纳假设显然仍可整除”，通常会把最重要的一步藏起来。

整除还允许我们使用一个简单事实：$a$ 的整数倍之和仍是 $a$ 的整数倍。也就是说，如果

且

其中 $r,s\in\mathbb Z$，那么

这就是整除归纳中“旧倍数 + 新倍数”的依据。

目标不是算出 $4^{k+1}-1$，而是把它改写成 $3$ 乘一个整数。

例题：证明 $3\mid(4^n-1)$

证明对所有正整数 $n$，

我们希望在 $4^{k+1}-1$ 中制造出归纳假设里的 $4^k-1$。把 $4^{k+1}$ 看成 就够了。

最后一句“$4q+1$ 是整数”并非多余。整除定义要求存在一个整数倍数，这句话正好把定义闭合。

例题：证明 $3\mid(n^3-n)$

证明对所有正整数 $n$，

不等式命题：归纳假设之后还要补一段放缩

等式归纳通常在代数整理后正好碰到目标。不等式归纳更常见的情况是：归纳假设只能把我们送到一个中间量，还要继续比较这个中间量与目标。

如果已知

而目标是

常见路线是

第一个不等号使用归纳假设，第二个不等号使用 $k$ 的范围或一个单独的代数事实。两个依据都要写出来。

图像能提示指数增长更快；归纳证明仍需把 $2^k\ge k+1$ 可靠地推进到 $2^{k+1}\ge k+2$。

例题：证明 $2^n\ge n+1$

证明对所有正整数 $n$，

起点会决定放缩能不能成立

证明对所有整数 $n\ge4$，

这一次不能从 $n=1$ 开始，因为命题在 $n=3$ 时不成立。起点 $4$ 还会在归纳步骤的第二段比较中发挥作用。

这也解释了为什么归纳步骤里的范围不能省略。若只写“设 $k$ 为整数”，就没有依据断言 $k(k-2)-1>0$。

例题：分组后的调和和下界

证明对所有整数 $n\ge1$，

这道题的下标容易看错。$n$ 增加到 $n+1$ 时，和式不是只多一项，而是从 $2^n+1$ 一直多到 $2^{n+1}$。

新增项的个数是

这些项中最小的是最后一项 $1/2^{k+1}$，所以新增部分至少是

错误证明检查：每一环都要真的接上

归纳证明形式整齐，反而容易把错误藏在熟悉的句式里。检查时不要只看它有没有“基础、假设、步骤”这些标签，要看标签下面的命题是否正确、范围是否覆盖第一条边。

错误一：把目标放进归纳假设

要证明

有人写：

这段话假设的就是 $P(k+1)$。它既没有使用 $P(k)$，也没有建立 $P(k)\Rightarrow P(k+1)$，所以是循环论证。正确的假设只能停在

然后从左边补上 $k+1$。

错误二：基础看似正确，实际选错了起点

考虑这个假命题：对所有整数 $n\ge0$，

有人把 $n=0$ 时的左边看成空和，于是说两边都是 $0$；接着又声称只要 $P(k)$ 成立，两边加 $k+1$ 就得到 $P(k+1)$。代数形式看起来很顺。

问题出在第一条真正需要的传递 $P(0)\Rightarrow P(1)$。当 $n=0$ 时，$2+3+\cdots+n$ 被解释为空和；当 $$ 时，它仍然是空和，并没有新增 。因此从 到 不能使用“加上 ”这条变形。实际上

是假的。

这类错误提醒我们：省略号表示的和式也有边界，不能默认从 $k$ 到 $k+1$ 永远恰好多出一项。最小的几个值要写开检查。

错误三：证明了大多数步，却漏掉第一步

有一个著名的错误论证试图证明“任意 $n$ 匹马颜色都相同”。它的想法是：从 $n+1$ 匹马中拿走最后一匹，前 $n$ 匹按归纳假设同色；再放回最后一匹并拿走第一匹，后 $n$ 匹也同色；两组有重叠，因此全部同色。

当 $n\ge2$ 时，两组确实有共同的马。但从 $n=1$ 推到 $n=2$ 时，两组分别只有第一匹和第二匹，交集为空。没有共同成员，就无法把两组的颜色连起来。

也就是说，这个论证至多证明了

却没有证明启动链条所必需的

“后面都能接上”不能弥补第一条边断开。

一份更可靠的检查表

写完后逐项回答：

1. $P(n)$ 是否包含完整命题与完整范围？
2. 起点 $n_0$ 是否是结论范围中的第一个整数？
3. $P(n_0)$ 是否真的成立，而不是只写“显然”？
4. 归纳步骤中的 $k$ 是否任意，并明确满足 ？

普通归纳卡住时，先检查命题够不够用

普通归纳不是把“假设 $P(k)$”写上去就一定能成功。真正困难的部分，是让 $P(k)$ 提供足够的信息推出 $P(k+1)$。

如果卡住，可以按这个顺序排查：

1. 目标写对了吗？ 先把 $P(k)$ 和 $P(k+1)$ 并排写出，找出新增项或新增结构。
2. 归纳假设用上了吗？ 如果整段证明完全不需要 $P(k)$，它可能是一个直接证明，也可能漏了关键逻辑。
3. 代数形式合适吗？ 求和式通常拆最后一项，整除式通常凑出旧表达式，不等式通常需要一个中间界。
4. 命题是否太弱？ 有时原命题只告诉你一个结果，却不给下一步所需的附加信息。这时可以尝试证明一个更强、但仍然为真的命题。
5. 下一步是否依赖更早的多个情形？ 如果 $P(k+1)$ 同时需要 、 或更早结论，强归纳会写得更自然。

本章的三个主要题型都只需上一格：求和时补一个新项，整除时把下一项写成旧倍数加新倍数，不等式时从旧界推出新界。下一章会遇到“拆开一个对象后，得到的几个部分大小不一”的问题。那时只知道 $P(k)$ 往往不够，我们会允许同时使用 $P(n_0),P(n_0+1),\ldots,P(k)$，这就是强归纳法。

练习

先在纸上写出 $P(n)$、起点、$P(k)$ 和 $P(k+1)$，再展开证明。答案折叠起来，是为了让你先检查自己的桥搭在哪里。

练习一：立方和

证明对所有正整数 $n$，

练习二：几何和

设 $r$ 是实数且 $r\ne1$。证明对所有非负整数 $n$，

练习三：整除

证明对所有正整数 $n$，

练习四：不等式

证明对所有整数 $n\ge2$，

练习五：找出断掉的第一条边

有人要证明“对所有正整数 $n$，任意 $n$ 个人年龄相同”。他用与“两组各去掉一人”相似的论证，声称从 $P(k)$ 可以推出 $P(k+1)$。错误发生在哪个 $k$？为什么？

本章小结

普通归纳法证明的是一族按整数排列的命题。它需要一个准确的起点 $P(n_0)$，还需要对任意 $k\ge n_0$ 建立 $P(k)\Rightarrow P(k+1)$。归纳假设不是循环论证，因为它只是证明这个条件命题时临时采用的前件；真正要推出的是不同的命题 。

求和公式通常拆出新增最后一项；整除命题先按定义写成某个整数倍；不等式命题往往要在使用归纳假设后再补一次有范围依据的放缩。每种题型的表面计算不同，骨架始终相同：起点要对，第一条边不能断，任意一步都必须接得上。

下一章会把“只允许使用 $P(k)$”扩展为“可以使用从起点到 $P(k)$ 的全部已知情形”。当下一步依赖多个更小对象时，那种写法会更自然。

所以 $P(1)$ 成立。

所以基础情形成立。

所以基础情形成立。注意每个非零整数都整除 $0$。

所以 $P(4)$ 成立。

那么

提取 $(k+1)^2$：

这正是 $P(k+1)$。由数学归纳法，公式对所有正整数 $n$ 成立。

任取整数 $k\ge0$，假设

给左边补上 $r^{k+1}$：

这就是 $P(k+1)$。因此公式对所有非负整数 $n$ 成立。

考察下一项：

因为 $6q+1$ 是整数，所以 $5\mid(6^{k+1}-1)$。由数学归纳法，命题对所有正整数 $n$ 成立。