数学归纳法 — 两步走完无穷多个断言
这一章讲三件事: 一条捷径怎么从「几个例子都对」变成「对所有情况都对」; 只用两步凭什么能管住无穷多个断言; 以及这套办法怎么反过来帮你写对一个循环。
它在全书链条里的位置: 第 06 章找出了周期、第 07 章找出了分类, 但那两章都只是「试出来的」——试算五个数看着有规律,凭什么相信第一亿个也一样? 这一章补上的正是那块地基:怎么把「看着像」变成「一定是」。 后面第 11 章的递归,是同一件事反着走; 而「不能靠试,必须证明」这条要求,第 15 到 17 章会一路用到底。
1. 先看现象:存钱罐里第 100 天有多少钱
一个空存钱罐,第 1 天投 1 元、第 2 天投 2 元、第 3 天投 3 元…… 第 100 天的时候,里面一共有多少钱?1
老实的办法是一个一个加:1 + 2 = 3,再加 3 得 6,再加 4 得 10…… 一直加到 100。这要做 99 次加法,能算出来,但很费劲2。
全章的主走查:1 + 2 + 3 + … + 100 = ?
────────────────────────────────────────────────
§2 首尾配对 → 101 × 100 ÷ 2 = 5050 ← 得到答案
§3 把 100 换成 n,写成一句对所有 n 的话 ← 得到断言
§4 两步走完无穷 ← 得到工具
§5 拿这条断言把两步各走一遍 ← 证完
────────────────────────────────────────────────
图说:这一章不是「算出 5050」就完了。
算出来只是第一步,把它变成「对所有 n 都成立」才是正题。
故事的主角是九岁的高斯——德国数学家,当年遇到同一道题, 没有计算器也没有计算机,马上就报出了答案3。
2. 小高斯的办法:把它掉个头,叠上去
这一节回答:那 99 次加法是怎么被绕开的。
小高斯的做法是:把这串数正着写一遍,再倒着写一遍,上下并排相加4:
1 + 2 + 3 + … + 99 + 100
+ 100 + 99 + 98 + … + 2 + 1
────────────────────────────────────
101 + 101 + 101 + … + 101 + 101 ← 100 个 101
每一列都是 101,一共 100 列,所以总和是 101 × 100 = 10 100。 但这是把原来那串加了两遍,所以要除以 2,得 50505。这是主走查的第一步。
换成图更好看: 1、2、3……100 块瓷砖摆成一个阶梯, 再做一个一模一样的阶梯倒扣上去,正好拼成一个长 100、高 101 的长方形6。
这条捷径省了多少? 老实加要 99 次加法;小高斯的办法是 一次加法(1 + 100)、一次乘法、一次除法,一共三步。
但真正的差距要换个规模才看得出来。 原书把 100 换成 100 亿: 就算计算器一秒做一次加法,老实加要花 300 年以上; 而小高斯的办法仍然是三步——一次加、一次乘、一次除7。
这就是这一章值钱的地方:省的不是力气,是数量级。
3. 从「100」到「所有的 n」:先学会把话说大
这一节回答:上一节那条捷径,凭什么相信它对别的数也管用。
先把话说大。 原书把「1 到 100」换成「0 到 n」—— 这里的 n 是一个还没定下来的数,用一个字母代替它,这个字母就叫变量8。 于是那条捷径变成一句话:
断言 G(n):0 到 n 的整数之和,等于 n × (n + 1) ÷ 2
代进 n = 100 试试: 100 × 101 ÷ 2 = 5050 ✓(和上一节一致)。 代进 n = 3: 0 + 1 + 2 + 3 = 6,而 3 × 4 ÷ 2 = 6 ✓。 这是主走查的第二步。
但「代几个数试试都对」不等于「对所有 n 都对」。 原书专门举了一个会翻车的例子9:
| 断言 | 试几个小的 | 真相 |
|---|---|---|
| 「n × 2 是偶数」 | n=0 对、n=1 对 | 对所有 n 都成立 |
| 「n × 3 是奇数」 | n=1 对(3 是奇数) | n=2 就塌了(6 是偶数) |
第二条只错在第二个数上。 那要是一条断言前一百万个数都对、第一百万零一个才塌呢? 试是试不出来的,因为 0 以上的整数有无穷多个10。
4. 两步:推倒第一张,再保证每一张都带倒下一张
这一节给出这一章唯一的工具,请慢读。
要证明「断言 P(n) 对 0 以上的所有整数 n 都成立」,只需要两步11:
步骤 1:证明 P(0) 成立 ← 原书管它叫「基底」
步骤 2:证明不论 k 是 0 以上的哪个整数,
「若 P(k) 成立,则 P(k+1) 也成立」 ← 原书管它叫「归纳」
图说:两步都成立,这条断言就对所有 n 成立了。
第一步是「起点没问题」,第二步是「每一步都迈得过去」。
这就是数学归纳法12。这是主走查的第三步:我们拿到工具了。
为什么两步就够?把它读成一串多米诺骨牌13:
- 步骤 1 = 确保第 0 张骨牌倒下;
- 步骤 2 = 确保只要第 k 张倒了,第 k+1 张一定跟着倒。
两条都做到,整排骨牌无论排多长,最后都会倒。 就算 n 是 10 000 000 000 000 000,机械地反复用步骤 2,终究能推到那里14。
这里有一条容易 读岔的地方,原书自己也承认当年卡在这儿: 步骤 2 里要「假设 P(k) 成立」,看起来像是把要证的东西当成前提用了——这不是循环论证。 步骤 2 证的不是「P(k) 成立」,而是「若 P(k) 成立则 P(k+1) 成立」这条连接15。 连接和结论是两回事:多米诺骨牌之间「挨得够近」是一回事,「第一张真的倒了」是另一回事。
还有一条差别值得留意:数学归纳法不关心花多少时间—— 就算推到第一亿张要一亿步,数学也不在乎。 原书说,这正是数学和编程之间最大的差异16(编程是要真跑的,时间就是钱)。
5. 拿小高斯那条断言,把两步各走一遍
这一节把工具用在主走查的那条断言上。
步骤 1(基底):证明 G(0) 成立。 G(0) 说的是「0 到 0 的整数之和等于 0 × 1 ÷ 2」。 左边是 0,右边也是 0。成立17。
步骤 2(归纳):假设 G(k) 成立,证明 G(k+1) 也成立。 假设「0 + 1 + … + k = k × (k+1) ÷ 2」这句话是对的,那么18:
G(k+1) 的左边 = 0 + 1 + … + k + (k+1)
└────────────┘
这一段按假设可以整个换成 k × (k+1) ÷ 2
= k × (k+1) ÷ 2 + (k+1)
= k × (k+1) ÷ 2 + 2 × (k+1) ÷ 2 ← 通分
= (k+1) × (k+2) ÷ 2 ← 提出 (k+1)
G(k+1) 的右边 = (k+1) × ((k+1)+1) ÷ 2
= (k+1) × (k+2) ÷ 2 ← 一样
两边算出来一样,步骤 2 成立。
拿具体的数看一眼这一步在干什么(k 取 3): 假设 G(3) 成立,也就是 0+1+2+3 = 6;那么 G(4) 的左边就是 6 + 4 = 10, 而 G(4) 的右边是 4 × 5 ÷ 2 = 10。对上了。
两步都证完了,所以 G(n) 对 0 以上的所有整数 n 都成立19。 这是主走查的第四步,也是终点:小高斯那条捷径,从「试着对」变成了「一定对」。
6. 换成程序员的读法:它就是一个循环
这一节回答:上面那套东西,和写代码是什么关系。
原书给了一段 C 代码,把数学归纳法整个翻译成了程序20:
void prove(int n)
{
int k;
printf(" 现在开始证明 P(%d) 成立。\n", n);
k = 0;
printf(" 根据步骤 1 得出 P(%d) 成立。\n", k); // ← 基底
while (k < n) {
printf(" 根据步骤 2 可以说“若 P(%d) 成立，则 P(%d) 也成立”。\n", k, k + 1);
printf(" 因此，可以说“P(%d) 是成立的”。\n", k + 1);
k = k + 1; // ← 归纳,一次爬一级
}
printf(" 证明结束。\n");
}
调用 prove(2),它会打印出三段话: 先说「根据步骤 1,P(0) 成立」,
再说「若 P(0) 成立则 P(1) 成立,所以 P(1) 成立」,
再说「若 P(1) 成立则 P(2) 成立,所以 P(2) 成立」21。
看着这段代码,那条「不是循环论证」的疑问会自己消失:
n 是你要爬到的那一级,k 是脚下正在踩的那一级。
原书说,他当年之所以想不通,就是把这两个混成了一件事22。
7. 反过来用:写循环时那句「每转一圈都成立的话」
这一节另起一处走查,是这一章对程序员最实在的部分。
写循环的时候,找到一句「每转一圈都成立」的话,非常重要—— 这句话叫循环不变式23。
看一个最简单的例子:把数组里的元素加起来24。
int sum(int array[], int size)
{
int k = 0;
int s = 0;
/* M(0):s 等于前 0 个元素之和 */
while (k < size) {
/* M(k):s 等于前 k 个元素之和 */
s = s + array[k];
/* M(k+1):s 等于前 k+1 个元素之和 */
k = k + 1;
}
/* M(size):s 等于全部元素之和 */
return s;
}
那句话是:「变量 s 的值,等于数组前 k 个元素之和」。
拿 [3, 1, 4] 走一遍(这三个数是我们为演示编的):
| 时刻 | k | s | 那句话成不成立 |
|---|---|---|---|
| 进循环前 | 0 | 0 | 前 0 个元素之和是 0 ✓ |
| 第一圈之后 | 1 | 3 | 前 1 个元素之和是 3 ✓ |
| 第二圈之后 | 2 | 4 | 3 + 1 = 4 ✓ |
| 第三圈之后 | 3 | 8 | 3 + 1 + 4 = 8 ✓ |
| 出循环 | 3 = size | 8 | 前 3 个之和 = 全部之和 ✓ |
这张表和第 4 节那两步严丝合缝: 进循环前那一行是基底(相当于步骤 1), 每一圈的「进去时成立 → 出来时还成立」是归纳(相当于步骤 2)25。
于是「这个循环写对了没有」变成了一句可检查的话。 原书还提醒了另一半:循环不变式管的是「达到目的」, 而 k 从 0 涨到 size 管的是「适时结束」——两件事都要26。
8. 当心:一个每一步都像模像样的错证明
这一节另起第二处走查,它是这一章最值钱的一节。
原书用数学归纳法「证明」了一件荒唐事:随便扔 n 枚黑白棋,颜色一定全相同27。 这个结论当然不成立——随手撒一把就能撒出两种颜色。但请你先自己找出错在哪一步。
步骤 1: n = 1 时,只有一枚棋子,颜色当然只有一种。这一步没毛病28。
步骤 2: 假设「任意 k 枚棋子颜色都相同」。现在有 k+1 枚, 把它们分成两组,每组 k 枚——第 1 到 k 枚是 A 组,第 2 到 k+1 枚是 B 组。 按假设,A 组 内部同色、B 组内部同色;而两组之间共有 k−1 枚棋子, 靠这些共有的棋子,两组的颜色被串成了同一种,所以 k+1 枚全同色29。
错在哪儿?
错在 k = 1 这一格上30。k = 1 时,A 组和 B 组各只有 1 枚, 两组共有的棋子是 k − 1 = 0 枚——根本没有共有的棋子。 没有共有的棋子,两组的颜色就串不起来,那句「所以全同色」当场断掉。
k = 3 时: [● ● ●] A 组
[● ● ●] B 组 共有 2 枚 → 串得起来
k = 1 时: [●] A 组
[○] B 组 共有 0 枚 → 串不起来!
图说:图画的是 k 比较大的情况,看起来天经地义;
而证明要求「对所有 k 都成立」,只要 k=1 这一格塌了,整条链就断了。
这一节的教训不是「归纳法不可靠」,是「图会骗人」。 原书的原话是:图虽然方便,但光靠图来解题是可能存在问题的31。 步骤 2 必须对每一个 k 都成立,包括最小的那个 k。
9. 作者的判断、我们的判断,以及这一章的边界
| 说法 | 书里给了什么 |
|---|---|
| 小高斯的配对法 | 给了两种推导(上下叠加、瓷砖拼长方形)+ 一个规模对照(100 亿要 300 年) |
| 两步就能证完无穷 | 给了理由(多米诺骨牌)+ 一段能跑的 C 代码 |
| 步骤 2 不是循环论证 | 给了作者本人的困惑与解法:混淆了目标层数 n 和途经层数 k |
| 循环不变式 | 给了一段逐行写着注释的代码,把每一行成立的断言都写在旁边 |
| 「图会骗人」 | 给了一个完整的错误证明,并指出错在 k=1 |
判断(我们的,不是书里的):这一章对程序员的 真正用途,不是去证明什么定理, 是在写循环之前先把那句「每转一圈都成立的话」说出来。 大多数循环 bug——少转一圈、多转一圈、边界没初始化—— 都会在你试图把那句话写清楚的时候暴露出来。 说不清那句话,通常意味着这个循环你其实没想明白。 如果错,会错在: 对于状态简单的循环(遍历一个列表打印), 硬要写不变式属于形式主义,收益接近零。 判据是:这个循环里有没有一个跨圈累积的量(比如
s)。
这一章的边界:
- 只讲了最基本的一种归纳(从 k 推到 k+1); 强归纳(用 0 到 k 全部来推 k+1)没提,而第 12 章的斐波那契其实要用到它;
- 没有讲归纳法本身为什么成立(它依赖整数的一条基本性质),原书用多米诺骨牌代替了;
- 循环不变式只给了一个最简单的例子,没有讲怎么给复杂循环找不变式;
- 「适时结束循环」只提了一句,没有展开讲终止性怎么证。
10. 可带走的
- 1 加到 100,首尾配对之后只要三步:一次加、一次乘、一次除,答案 5050;
- 省的不是力气,是数量级:换成加到 100 亿,老实加要 300 年,配对法还是三步;
- 「试几个数都对」不等于「对所有数都对」——「n × 3 是奇数」在 n=2 就塌了;
- 数学归纳法只要两步:证 P(0) 成立(基底),证「P(k) 成立则 P(k+1) 成立」(归纳);
- 读成多米诺骨牌:推倒第一张,再保证每一张都带倒下一张;
- 步骤 2 不是循环论证——它证的是「连接」,不是「结论」;
- 它就是一个 while 循环:
k从 0 涨到n,每圈用一次步骤 2; - 反过来用:写循环前先说出那句「每转一圈都成立的话」,它叫循环不变式;
- 图会骗人:那个「所有棋子同色」的错误证明,毛病只在 k=1 那一格上;
- 步骤 2 必须对每一个 k 都成立,包括最小的那个。
11. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 存钱罐与小高斯 | 第4章 数学归纳法 | text/09-ch04.txt:39(搜「第 100 天时的总金额为多少呢」) · :47(搜「德国数学家高斯在 9 岁时」) |
| 首尾配对与 5050 | 第4章 数学归纳法 | text/09-ch04.txt:62(搜「100 个 101 相加的结果」) · :64(搜「答案：5050 元」) · :90(搜「纵向有 101 块瓷砖」) |
| 加到 100 亿的对照 | 第4章 数学归纳法 | text/09-ch04.txt:95(搜「加到 100 亿也」) · :97(搜「也只要 1 次加法、1 次乘法、1 次」) |
| 0 以上整数的断言、反例 | 第4章 数学归纳法 | text/09-ch04.txt:144(搜「n × 2 为偶数」) · :154(搜「n × 3 为奇数」) · :160(搜「反例之一」) |
| 数学归纳法的两步 | 第4章 数学归纳法 | text/09-ch04.txt:199(搜「步骤 1」) · :206(搜「我们将步骤 1 称作基底」) · :208(搜「我们将步骤 2 称作归纳」) |
| 多米诺骨牌 | 第4章 数学归纳法 | text/09-ch04.txt:232(搜「推倒多米诺骨牌」) · :243(搜「数学归纳法并不像」) |
| 证明小高斯的断言 | 第4章 数学归纳法 | text/09-ch04.txt:256(搜「证明 G(0) 成立」) · :305(搜「左边和右边的计算结果相同」) |
| prove 函数 | 第4章 数学归纳法 | text/09-ch04.txt:463(搜「void prove(int n)」) · :513(搜「从 prove 函数的运行结果」) · :540(搜「混为一谈了」) |
| 循环不变式 | 第4章 数学归纳法 | text/09-ch04.txt:548(搜「循环不变式」) · :572(搜「数组 array 的前 n 个元素之和」) · :635(搜「一个是「达到目的」」) |
| 错误的归纳证明 | 第4章 数学归纳法 | text/09-ch04.txt:402(搜「所有棋子的颜色一定相同」) · :438(搜「该图在 k = 1 时不成立」) · :450(搜「光靠图来解题是可能存在问题的」) |