Lecture 3: Induction（归纳法）

目录 · ← l3 · l5 →

Lecture 3: Induction（归纳法）

概述

前两讲（L00 直接证明、L01 命题逻辑、L02 逆否/反证/分情形）解决的都是单个命题的证明问题。但 CS70 里绝大多数命题不是关于一个数、而是关于无穷多个自然数的：$\forall n \in \mathbb{N}, P(n)$。逐一验证不可能——自然数有无穷多个，而人只能写有限步。

本讲引入的 数学归纳法 (Mathematical Induction) 就是解决这类问题的核心工具：用有限的手段论证无穷多的情形。它的第二个形态 强归纳法 (Strong Induction) 把归纳假设从”$P(k)$ 成立”加强为”$P(0),P(1),\dots,P(k)$ 全部成立”，从而能处理”$n$ 依赖多个更小的情形”的问题。本讲还给出归纳法与递归 (Recursion) 的对应关系——这正是归纳法能用来证明递归程序正确性的原因，也是 CS70 里”数学”与”计算机科学”最直接的接口。

L03 是”证明工具箱”（L00–L03）的最后一块，也是后面每一个算法正确性证明的模板：L05 的 Euclid 算法、L06 的 RSA 解密正确性、L08 的 Berlekamp–Welch 纠错、L09–L10 的图论（树的边数、握手引理）、L11 的 Gale–Shapley 稳定匹配、L14 的组合恒等式、L20 的期望线性性，全部依赖归纳法。

核心概念的直观解释

概念一：数学归纳法 (Mathematical Induction)

• 定义：要证明 $\forall n \in \mathbb{N},\, P(n)$，只需完成两件事：
  1. 基础情形 (Base Case)：证明 $P(0)$（或某个适当的起始值 $n_0$）为真。
  2. 归纳步骤 (Inductive Step)：对任意 $k \ge 0$，证明 $P(k) \Rightarrow P(k+1)$。其中”假设 $P(k)$ 成立”这一条叫做 归纳假设 (Induction Hypothesis, IH)。 两步都完成后，由数学归纳法公理 (axiom of mathematical induction) 断言 $\forall n \in \mathbb{N}, P(n)$。
• 直观解释（多米诺骨牌）：把 $P(0), P(1), P(2), \dots$ 想象成排成一列的多米诺骨牌。
  • 基础情形 = 你伸手推倒第 0 张牌。
  • 归纳步骤 = 牌与牌之间的距离排得足够近，保证第 $k$ 张倒下时必然撞倒第 $k+1$ 张。这一步与”牌实际倒没倒”无关——它是一条关于排列方式的静态事实。
  • 结论 = 第 0 张倒下引发连锁反应，全部倒下。 三个要素缺一不可：只推倒第 0 张而牌距太远（$P(k)\not\Rightarrow P(k+1)$），链条断在第一格；牌距排得再好而没人推第一张（漏掉基础情形），一张都不会倒。
• 具体示例：证明 $1 + 3 + 5 + \cdots + (2n-1) = n^2$。基础情形 $n=1$：左边 $=1$，右边 $=1$。归纳步骤：假设 $1+3+\cdots+(2k-1) = k^2$，则加上第 $k+1$ 个奇数 $2k+1$ 得 $k^2 + 2k + 1 = (k+1)^2$，正是 $n=k+1$ 时的结论。两步齐备，全部 $n \ge 1$ 成立。

概念二：良序原理 (Well-Ordering Principle) —— 归纳法的合法性来源

• 定义：$\mathbb{N}$ 的每一个非空子集都有一个最小元素。
• 直观解释：自然数是从 $0$ 开始、一格一格往上的，不能无限向下走。所以任何一堆自然数里总能揪出最小的那个。（对比：整数集 $\mathbb{Z}$ 和正有理数集 $\mathbb{Q}_{>0}$ 都不满足良序原理——$\mathbb{Z}$ 没有最小元，$\{1, 1/2, 1/3, \dots\}$ 没有最小元。）
• 它如何为归纳法背书（必须会写这段论证）： 设我们已经证明了 $P(0)$，也证明了 $\forall k,\, P(k)\Rightarrow P(k+1)$。反证：假设结论不成立，即存在自然数 $n$ 使 $P(n)$ 为假。 考虑集合 $S := \{n \in \mathbb{N} : P(n) \text{ 为假}\}$，即”所有反例”的集合。由假设 $S$ 非空，故由良序原理，$S$ 有最小元素，记作 $m$。 由于 $P(0)$ 为真，$m \ne 0$，所以 $m \ge 1$，从而 $m - 1 \in \mathbb{N}$。 由 $m$ 的最小性，$m-1 \notin S$，即 $P(m-1)$ 为真。 但归纳步骤说 $\forall k,\, P(k) \Rightarrow P(k+1)$；取 $k = m-1$ 得 $P(m-1) \Rightarrow P(m)$，故 $P(m)$ 为真。 这与 $P(m)$ 为假（$m \in S$）矛盾。 所以 $S$ 必须是空集，即不存在反例，$\forall n \in \mathbb{N},\, P(n)$ 成立。
• 具体示例（应用同一论证模式）：证明”每个大于 1 的整数都有质因子”。设反例集非空，取最小反例 $m$；若 $m$ 是质数则它就是自己的质因子，矛盾；否则 $m = ab$ 且 $1<a<m$，由 $m$ 的最小性 $a$ 有质因子，而该质因子也整除 $m$，矛盾。这个”取最小反例”的套路与上面的论证完全同构，是本课程反复出现的证明骨架。

概念三：强归纳法 (Strong Induction)

• 定义：要证明 $\forall n \ge n_0,\, P(n)$：
  1. 基础情形：证明 $P(n_0)$（有时候需要证明多个基础情形，例如 $P(n_0), P(n_0+1), \dots$）。
  2. 归纳假设（强化版）：对任意 $k \ge n_0$，假设 $P(n_0), P(n_0+1), \dots, P(k)$ 全部为真，即 $\bigwedge_{i=n_0}^{k} P(i)$。
  3. 归纳步骤：在 (2) 的假设下证明 $P(k+1)$。
• 直观解释：多米诺版的说法是——简单归纳依赖”第 $k$ 张撞倒第 $k+1$ 张”（只用到紧邻的前一张）；强归纳依赖”第 $n_0$ 到第 $k$ 张全部倒下时，第 $k+1$ 张必然倒下”（用到前面所有牌）。
• 逻辑等价性（重要）：强归纳与简单归纳在证明能力上完全等价，强归纳能证的简单归纳都能证，反之亦然。直观理由：如果简单归纳的链条真的成立了，那么第 0 张倒下会依次撞倒第 1、2、…、$k$ 张，等到要处理第 $k+1$ 张时，前面所有牌都已经倒了——这正是强归纳假设的内容。形式化的说法：令 $Q(n) := P(0) \wedge P(1) \wedge \cdots \wedge P(n)$，则”对 $P$ 的强归纳”等价于”对 $Q$ 的简单归纳”。
• 那为什么还要用它？ 因为强归纳的归纳假设更强，所以用起来更省力。官方给的比喻很贴切：螺丝刀和电动螺丝刀——它们能完成的任务集合相同，但后者用起来轻松得多。典型场景是”$n$ 的结论依赖某个比 $n$ 小但不一定等于 $n-1$ 的量”（例如 $n = ab$，$a,b$ 都可能远小于 $n$），此时简单归纳的 $P(k)$ 根本不够用。
• 具体示例：证明每个 $n \ge 12$ 可写成 $4x+5y$。归纳步骤要处理 $n = k+1$，但唯一的出路是回退到 $n-4$（即 $k-3$），这不是 $k$，简单归纳假设 $P(k)$ 完全使不上力；而强归纳假设允许我们使用 $P(k-3)$（只要 $k-3 \ge 12$）。详见后文。

概念四：强化归纳假设 (Strengthening the Induction Hypothesis)

• 定义：当”直觉上更弱”的目标命题 $P(n)$ 用归纳法证不动时，转而证明一个更强但更有结构的命题 $P^{\prime}(n)$（满足 $P^{\prime}(n) \Rightarrow P(n)$）。由于待证更强，归纳假设也更强，归纳步骤反而更容易完成。
• 直观解释：这是归纳法最反直觉的一点——证一个更强的命题反而更容易。原因在于 $P(n)$ 太”模糊”（例如只说”是平方数”而不说”是哪一个平方数”），归纳假设携带的信息量不足以推出 $P(k+1)$。强化后的 $P^{\prime}(n)$ 把结构写清楚了（”恰好等于 $n^2$”），于是 $k^2 + (2k+1) = (k+1)^2$ 一步到位。
• 代价与收益：代价是你必须多证一些东西（$P^{\prime}$ 比 $P$ 强），收益是归纳假设变得可用。实践中判断是否需要强化的信号是：归纳步骤卡住了，卡住的位置恰好是”缺少关于 $k$ 的精确信息”。
• 具体示例：目标”前 $n$ 个奇数之和是完全平方数”证不动；强化为”前 $n$ 个奇数之和 $= n^2$”后立刻证通。另一个例子：目标 $\sum_{i=1}^n 1/i^2 \le 2$ 证不动；强化为 $\sum_{i=1}^n 1/i^2 \le 2 - 1/n$ 后证通。两例详见后文。

概念五：归纳法与递归 (Recursion) 的对应

• 定义：递归是用自身定义自身的函数定义方式：$F(n)$ 的值由 $F$ 在更小参数上的值决定，并配以基础值。例如 $F(0)=0,\ F(1)=1,\ F(n) = F(n-1)+F(n-2)$。
• 直观解释：归纳法”自底向上爬”（从 $P(0)$ 爬到 $P(n)$），递归”自顶向下拆”（把 $F(n)$ 拆成更小的 $F$）。两者是同一个数学事实的两面：递归定义之所以良定义（不会无限向下递归），依据正是良序原理；递归程序的正确性证明，结构上就是一次归纳（通常是强归纳，因为递归调用可能落在任意更小的参数上）。
• 具体示例：递归的 F(n) = F(n-1) + F(n-2) 对应归纳中的”用 $P(k-1)$ 和 $P(k-2)$ 推 $P(k)$”。这就是为什么递归程序的正确性几乎总要靠强归纳来证。

完整证明与推导（核心）

一、归纳法第一例：前 $n$ 个自然数之和

定理 3.1（官方 Note 4 的 Theorem 4.1）：$\forall n \in \mathbb{N},\ \displaystyle\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$。

证明策略：用简单归纳法，对变量 $n$ 做归纳。为什么需要归纳？因为命题对无穷多个 $n$ 都要成立，而验证前几个值是不够的。

为什么”验证前几项”不够：官方的 $n^2-n+41$ 反例

官方在引入归纳法之前先用一个警告性例子说明”检查前几项”的不可靠：考虑命题 $\forall n \in \mathbb{N},\ n^2 - n + 41$ 是质数。

脚本验算结果：

也就是说，$n = 0,1,2,\dots,40$ 全部给出质数（整整 41 个连续的成功案例！），但 $n=41$ 时立刻崩溃：$41^2 - 41 + 41 = 41^2 = 1681$ 是合数。这个例子的教训是：有限次验证永远无法排除无穷多个情形中的反例。归纳法的价值就在于它用一个有限的论证（基础情形 + 归纳步骤）覆盖了所有 $n$。

逐步推导：

记 $P(n)$ 为命题 $\displaystyle\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$。我们对 $n$ 做归纳。

1. 基础情形 $(n = 0)$：左边 $= \displaystyle\sum_{i=0}^{0} i = 0$（空和到 $0$ 即只有 $i=0$ 这一项，值为 0）；右边 $= \dfrac{0 \cdot 1}{2} = 0$。左边 $=$ 右边 ✓，故 $P(0)$ 成立。

2. 归纳假设 (IH)：对某个任意的 $k \ge 0$，假设 $P(k)$ 成立，即 \(\sum_{i=0}^{k} i = \frac{k(k+1)}{2}.\) 注意这里 $k$ 是任意的但固定的——我们不能取 $k$ 为具体数字（如 $k=5$），否则证明只能覆盖那一个值。

3. 归纳步骤：证明 $P(k+1)$，即证明 $\displaystyle\sum_{i=0}^{k+1} i = \frac{(k+1)(k+2)}{2}$。推导如下： \(\begin{aligned} \sum_{i=0}^{k+1} i &= \left(\sum_{i=0}^{k} i\right) + (k+1) & &(\text{把最后一项 } i=k+1 \text{ 拆出来；加法结合律})\\ &= \frac{k(k+1)}{2} + (k+1) & &(\text{代入归纳假设 IH})\\ &= \frac{k(k+1) + 2(k+1)}{2} & &(\text{通分，} k+1 = \tfrac{2(k+1)}{2})\\ &= \frac{(k+1)(k+2)}{2} & &(\text{提取公因子 } k+1) \end{aligned}\) 末行正是 $P(k+1)$ 的右边。故 $P(k) \Rightarrow P(k+1)$。

4. 结论：由数学归纳法原理，$\forall n \in \mathbb{N},\ P(n)$ 成立。$\blacksquare$

【证明机制解说】：这个证明的唯一关键步骤是第 3 步的第一个等号——把 $\sum_{i=0}^{k+1} i$ 拆成 $\left(\sum_{i=0}^{k} i\right) + (k+1)$。这个”拆出最后一项“的动作是几乎所有求和型归纳证明的起手式：它把新命题 $P(k+1)$ 的左边改写成”归纳假设能处理的部分 + 剩下的一项”。若不拆，$\sum_{i=0}^{k+1} i$ 与 $\sum_{i=0}^{k} i$ 之间就没有任何可用的桥。第二个等号则是归纳假设唯一被用到的地方，也是整个证明的”动力输入口”。

算例验算（脚本已核）：

二、归纳法第二例：$n^3 - n$ 被 3 整除

定理 3.2（官方 Note 4 的 Theorem 4.2）：对所有 $n \in \mathbb{N}$，$n^3 - n$ 被 3 整除。

证明策略：用简单归纳法。官方采用纯代数分解的路线（不显式分情形），我们先把官方路线写全；随后额外补充一条分情形的路线，以展示”同一命题、两种归纳步骤写法”，也回应”为什么这个命题天然与模 3 相关”。

逐步推导（官方代数路线）：

记 $P(n)$ 为命题 $3 \mid (n^3 - n)$。我们对 $n$ 做归纳。

1. 基础情形 $(n = 0)$：$P(0)$ 断言 $3 \mid (0^3 - 0)$，即 $3 \mid 0$。按整除的定义（$a \mid b$ 当且仅当存在整数 $q$ 使 $b = aq$），取 $q = 0$ 得 $0 = 3 \cdot 0$，故成立。（注意：非零整数都整除 0，这一点是定义直接给出的，不是”显然”。）

2. 归纳假设 (IH)：对某个任意的 $k \ge 0$，假设 $P(k)$ 成立，即 $3 \mid (k^3 - k)$。按定义，这等价于存在整数 $q$ 使得 \(k^3 - k = 3q.\) （把整除翻译成一个等式，是这类证明的必备动作——整除本身不能参与代数运算，等式才能。）

3. 归纳步骤：证明 $P(k+1)$，即 $3 \mid ((k+1)^3 - (k+1))$。从 $(k+1)^3$ 的二项式展开出发： \(\begin{aligned} (k+1)^3 - (k+1) &= k^3 + 3k^2 + 3k + 1 - (k+1) & &(\text{展开 } (k+1)^3 = k^3+3k^2+3k+1)\\ &= k^3 + 3k^2 + 3k - k & &(\text{消去 } +1 \text{ 与 } -1)\\ &= (k^3 - k) + 3k^2 + 3k & &(\text{重新分组，目的：凑出 } k^3-k)\\ &= 3q + 3(k^2 + k) & &(\text{代入 IH：} k^3-k = 3q)\\ &= 3\left(q + k^2 + k\right) & &(\text{提取公因子 } 3) \end{aligned}\) 因 $q, k$ 都是整数，$q + k^2 + k \in \mathbb{Z}$（整数对加法与乘法封闭）。故 $(k+1)^3 - (k+1)$ 是 3 的整数倍，即 $3 \mid ((k+1)^3-(k+1))$，$P(k+1)$ 成立。

4. 结论：由归纳法原理，$\forall n \in \mathbb{N},\ 3 \mid (n^3-n)$。$\blacksquare$

【证明机制解说】：关键是第三个等号处的“凑项”：把 $k^3 + 3k^2 + 3k - k$ 重新分组为 $(k^3-k) + (3k^2+3k)$。这不是随意的变形——它精确地把表达式切成两块：第一块 $(k^3-k)$ 正是归纳假设能处理的形式，第二块 $3k^2+3k$ 天然含因子 3，不需要任何假设。“把目标表达式拆成’归纳假设形式’ + ‘显然成立部分’“是代数型归纳证明的通用套路，与本讲定理 3.1 中”拆出最后一项”是同一思想。

补充路线（分情形，展示命题与模 3 的内在联系）：

注意到 $n^3 - n = n(n-1)(n+1)$，即三个连续整数之积。这个因式分解立刻解释了命题：三个连续整数中必有一个被 3 整除（把”被 3 除的余数”当盒子只有 3 个，连续三个数落进去，鸽笼原理的加强形式给出必有 $\lceil 3/3 \rceil = 1$ 个余数为 0——更直接地说，余数按 $0,1,2$ 循环）。于是归纳步骤可以这样写：

归纳步骤（分情形版）：要证 $3 \mid ((k+1)^3-(k+1))$。按 $(k+1) \bmod 3$ 的取值分三种情形（穷尽且互斥，因为任何整数模 3 的余数只能是 $0,1,2$）：

• 情形 (i)：$k+1 \equiv 0 \pmod 3$。则 $3 \mid (k+1)$，而 $(k+1)^3 - (k+1) = (k+1)\left[(k+1)^2 - 1\right]$ 含因子 $k+1$，故 $3 \mid ((k+1)^3-(k+1))$ ✓。
• 情形 (ii)：$k+1 \equiv 1 \pmod 3$。则 $k \equiv 0 \pmod 3$，故 $3 \mid k$。而 $(k+1)^3-(k+1) = k(k+1)(k+2)$ 含因子 $k$ ✓。
• 情形 (iii)：$k+1 \equiv 2 \pmod 3$。则 $k+2 \equiv 1+2 = 3 \equiv 0 \pmod 3$，故 $3 \mid (k+2)$。而 $(k+1)^3-(k+1) = k(k+1)(k+2)$ 含因子 $k+2$ ✓。

（注意：这条路线其实没有用到归纳假设——它是对所有 $n$ 直接成立的事实：$n(n-1)(n+1)$ 中必有一个是 3 的倍数。这提示我们：遇到整除型命题时，先试试因式分解，可能一步就能绕开归纳。但作为展示”归纳步骤如何与分情形结合”的范例，它非常典型——L03 后面定理 3.6、3.7 的归纳步骤都要分情形。）

算例验算（脚本已核，$n=0$ 到 $8$）：

代数恒等式验算：$(k+1)^3 - (k+1) = (k^3-k) + 3k^2+3k$ 对 $k = 0,1,2,3,4,5$ 逐一核对：$(0,0),(6,6),(24,24),(60,60),(120,120),(210,210)$，两边完全一致 ✓。

三、归纳法第三例：两色定理（几何命题的归纳证明）

背景：四色定理 (Four Color Theorem) 断言任何地图都能用 4 种颜色着色，使相邻（共享非平凡边界——不止一个点）的国家颜色不同。它从 1852 年提出后困扰数学界百余年，多份”证明”被提交又被推翻，直到 1976 年才由 Appel 与 Haken 给出计算机辅助证明。本讲证明它的一个简化版本：如果”地图”是矩形被若干直线划分而成，那么 2 种颜色就够了。

定理 3.3（官方 Note 4 的 Theorem 4.3）：设 $P(n)$ 表示命题”任何形如上述（矩形被 $n$ 条直线分割）的地图都是两色可着色的”。则 $\forall n \in \mathbb{N},\ P(n)$ 成立。

证明策略：用简单归纳法，归纳变量是直线数 $n$。这里的难点不是代数，而是几何对象的”减一”操作：给定一个 $n = k+1$ 条线的地图，我们要先”删掉一条线”退回到 $k$ 条线的地图，对后者用归纳假设，再把线放回去并修补着色。这类”构造性的减一 → 修补”是几何归纳证明的标准范式。

逐步推导：

1. 基础情形 $(n = 0)$：没有直线时，整个矩形就是一个区域，用单一颜色涂满即可。$P(0)$ 成立。✓

2. 归纳假设 (IH)：对某个任意的 $k \ge 0$，假设 $P(k)$ 成立，即任何被 $k$ 条直线分割的地图都能两色着色。

3. 归纳步骤：证明 $P(k+1)$。任取一张被 $k+1$ 条直线 $\ell_1, \dots, \ell_{k+1}$ 分割的地图 $M$。
   • 删除一条线：从 $M$ 中去掉最后一条线 $\ell_{k+1}$，得到地图 $M^{\prime}$，它只被 $k$ 条直线分割。
   • 应用归纳假设：由 IH，$M^{\prime}$ 存在一个合法的两色着色（红 / 蓝），即任意两个共享边界的区域颜色不同。
   • 观察”翻转不变性”：给定一个合法着色，如果把所有区域的红蓝互换（红 $\to$ 蓝，蓝 $\to$ 红），得到的仍然是一个合法着色。理由：合法性只要求”相邻区域颜色不同“，而互换保持了”不同”这个关系（红蓝互换是一一对应的双射）。同理，只对地图的某一部分翻转颜色，只要翻转的部分与未翻转部分之间没有”相邻”跨越，就仍然合法。
   • 放回 $\ell_{k+1}$ 并修补：把 $\ell_{k+1}$ 放回。这条直线把整个矩形分成两个半平面 $H^+$ 与 $H^-$。规则是：$H^-$ 一侧的所有区域保持 $M^{\prime}$ 中的颜色不动，$H^+$ 一侧的所有区域红蓝互换。
4. 验证合法性：任取两个共享非平凡边界的区域 $A, B$，检查它们颜色是否不同。按共享边界落在哪条线上分两种情形（穷尽且互斥——每条直线要么是 $\ell_{k+1}$，要么是前 $k$ 条之一）：
   • 情形 1：共享边界落在直线 $\ell_{k+1}$ 上。此时 $A,B$ 分别位于 $H^+$ 与 $H^-$（因为 $\ell_{k+1}$ 是它们的分界）。在 $M^{\prime}$ 中 $A,B$ 属于同一区域（被 $\ell_{k+1}$ 切开之前是一块），颜色相同，设为红。放回后，$H^-$ 侧的保持红，$H^+$ 侧的翻转为蓝。两者颜色不同 ✓。
   • 情形 2：共享边界落在前 $k$ 条直线中的某条上。此时 $A, B$ 在 $M^{\prime}$ 中就已经是相邻的不同区域（删掉 $\ell_{k+1}$ 并不改变它们之间的这条边界）。由 IH，它们在 $M^{\prime}$ 的着色中颜色不同。放回 $\ell_{k+1}$ 后需要检查翻转有没有破坏这一点。关键在于：$A,B$ 的共享边界是一条不落在 $\ell_{k+1}$ 上的线段，除端点外它完全位于 $\ell_{k+1}$ 的某一侧，因此 $A$ 与 $B$ 落在 $\ell_{k+1}$ 的同一侧，于是它们要么同被翻转、要么同不被翻转。红蓝互换是一一对应的双射，”颜色不同”这一关系在”两边同时互换”下保持不变，故 $A,B$ 颜色仍然不同 ✓。
5. 结论：由归纳法原理，$\forall n \in \mathbb{N},\ P(n)$ 成立。$\blacksquare$

ASCII 图示（两色定理的归纳步骤）：

 用最小规模看机制: 矩形先被 1 条水平线 l1 分成上下两块 (k=1)
   +---------------------------+   由 IH 得到的一个合法两色着色:
   |            R              |     上块 R, 下块 B (跨 l1 颜色不同 ✓)
   |                           |
   |===========================|   <-- l1 (水平线)
   |                           |
   |            B              |
   +---------------------------+

                         |  现在放回第 (k+1) 条线 l2 (竖直线),
                         |  规则: l2 左侧颜色不动, 右侧 R<->B 翻转
                         v

   +-------------+-------------+
   |      R      #      B      |   跨 l2: R 与 B 不同 ✓
   |             #             |
   |=============#=============|   <-- l1
   |             #             |
   |      B      #      R      |   跨 l2: B 与 R 不同 ✓
   +-------------+-------------+
                 ^
              l2 (第 (k+1) 条线)

 四对相邻检查:
   上左/上右 跨 l2 : R vs B  ✓      下左/下右 跨 l2 : B vs R  ✓
   上左/下左 跨 l1 : R vs B  ✓      上右/下右 跨 l1 : B vs R  ✓
 => 全部相邻区域颜色不同, 两色着色合法

手工核对（$k=1 \to 2$）：$M^{\prime}$ 是 $k=1$ 条线的地图，着色为上 $R$、下 $B$（脚本验证：$n=1$ 时区域数 $=2$）。放回 $\ell_2$ 后，左侧保持 $(R,B)$，右侧翻转为 $(B,R)$。四个区域两两相邻关系全部满足”不同色”，构造成功。这也是归纳步骤在最小规模上的自检。

算例（$n$ 条一般位置直线的区域数与着色）：$n$ 条直线若两两相交且无三条共点，把平面分成 $\dfrac{n(n+1)}{2} + 1$ 个区域：

（脚本已核。）注意一个常见误解：区域数是奇数（如 $n=3$ 时 7 个区域）不构成障碍。两色定理只要求”相邻区域颜色不同”，不要求两种颜色数量相等，也不要求区域数与颜色数有任何整除关系。

【证明机制解说】：整个证明的”灵光一现”是那句看似平淡的观察——“合法着色在红蓝全局互换后仍是合法着色”。这条性质之所以有用，是因为它给了我们一个自由度：我们可以对地图的任意”独立部分”单独翻转而保持合法性。于是”删线 → 着色 → 放线 → 翻转一侧”这四步就能把 $k$ 条线的解升级为 $k+1$ 条线的解。这个手法的本质是：归纳步骤不需要从零构造 $n+1$ 的解，只需要把 $n$ 的解”修补”成 $n+1$ 的解。几乎所有几何归纳证明（以及后续图论中的树、平面图定理）都遵循这个”删一点/删一边 → 修补”的模式。

为什么这是四色定理的简化版：一般地图中，一个国家（区域）可以有任意多个邻国，因此”删掉一个国家、补色”的自由度不够；而直线划分的结构保证了每个区域都是凸的，被一条线切开恰好产生两块，且”翻转一侧”这个全局操作总是有效。四色定理的困难恰恰在于这种全局修补策略在一般地图上失效。

四、强化归纳假设：两个范例

（A）第一个范例：前 $n$ 个奇数之和

尝试一（失败的证明）：

目标：对所有 $n \ge 1$，前 $n$ 个奇数之和是一个完全平方数 (perfect square)。 基础情形 $(n=1)$：第一个奇数是 1，$1 = 1^2$ 是完全平方数 ✓。 归纳假设：假设前 $k$ 个奇数之和是完全平方数，设为 $m^2$。 归纳步骤：第 $k+1$ 个奇数是 $2k+1$。由 IH，前 $k+1$ 个奇数之和为 $m^2 + 2k + 1$。卡住了——$m^2 + 2k + 1$ 为什么必须是完全平方数？我们只知道 $m$ 是某个整数，与 $k$ 之间没有任何已知关系，无法判断 $m^2+2k+1$ 是不是平方数。

诊断：归纳假设太”弱”——它只说”是平方数”，没有告诉我们是哪个平方数。信息量不足，无法推进到 $k+1$。

先做小规模计算，寻找结构：

（脚本已核到 $n=8$：和为 $64$。）小规模计算揭示了一个比原命题更强的结构：和不只是”某个平方数”，而是恰好等于 $n^2$。这就给出了强化的方向。

定理 3.4（官方 Note 4 的 Theorem 4.4）：对所有 $n \ge 1$，前 $n$ 个奇数之和等于 $n^2$。

证明策略：用简单归纳法，但证明的是强化后的命题（把”是完全平方数”精确化为”等于 $n^2$”）。强化后归纳假设携带了 $k$ 的精确信息，$k^2 + (2k+1)$ 就能用完全平方公式直接收口。

逐步推导：

1. 基础情形 $(n = 1)$：第一个奇数是 $1$，而 $1 = 1^2$ ✓。
2. 归纳假设 (IH)：假设前 $k$ 个奇数之和 $= k^2$，即 $1 + 3 + 5 + \cdots + (2k-1) = k^2$。
3. 归纳步骤：第 $k+1$ 个奇数是 $2(k+1)-1 = 2k+1$。由 IH， \(1 + 3 + \cdots + (2k-1) + (2k+1) = k^2 + (2k+1).\) 而右边正是完全平方公式的展开式： \(k^2 + 2k + 1 = (k+1)^2.\) 故前 $k+1$ 个奇数之和 $= (k+1)^2$，$P(k+1)$ 成立。
4. 结论：由归纳法原理，对所有 $n \ge 1$，前 $n$ 个奇数之和 $= n^2$。$\blacksquare$

【证明机制解说】：对比两次尝试的归纳步骤：失败的版本卡在 $m^2 + 2k+1$（$m$ 与 $k$ 无关，无从下手）；成功版本一步得到 $k^2 + (2k+1) = (k+1)^2$。差别完全在于归纳假设携带了多少信息。这就是”强化假设”的核心机制：待证命题越具体，归纳假设就越有力。请注意逻辑上的微妙之处——我们证明了一个更强的命题（”等于 $n^2$”），它蕴含原来的弱命题（”是平方数”），所以原命题也顺带得证。“证更强的命题”不是绕路，而是唯一可行的路。

（B）第二个范例：平方倒数和的上界

尝试一（失败的证明）：

目标：对所有 $n \ge 1$，$\displaystyle\sum_{i=1}^{n} \frac{1}{i^2} \le 2$。 归纳假设：假设 $\sum_{i=1}^{k} 1/i^2 \le 2$。 归纳步骤：要证 $\sum_{i=1}^{k} 1/i^2 + \dfrac{1}{(k+1)^2} \le 2$。由 IH，左边 $\le 2 + \frac{1}{(k+1)^2}$。卡住了——$2 + \frac{1}{(k+1)^2} > 2$，超出了我们要证的上界。

诊断：IH 只说”$\le 2$”，但 $\le 2$ 这个界太松。必须追问：$\sum_{i=1}^k 1/i^2$ 有可能恰好等于 2 吗？如果可以，那加上正项 $\frac{1}{(k+1)^2}$ 就必然超过 2，证明无救。脚本验算显示实际部分和远小于 2：

（真正的极限是 $\pi^2/6 \approx 1.644934$，也远小于 2；但这需要 L24 之后的级数工具。）同时我们看到一个更强的、带”余量”的上界正在成立：$\sum_{i=1}^n 1/i^2 \le 2 - 1/n$。这正是强化的方向——把固定界 2 换成一个随 $n$ 收紧的界 $2 - 1/n$，从而为下一步留出空间。

定理 3.5（官方 Note 4 的 Theorem 4.5）：对所有 $n \ge 1$，$\displaystyle\sum_{i=1}^{n} \frac{1}{i^2} \le 2 - \frac{1}{n}$。

证明策略：用简单归纳法 + 强化归纳假设。强化的作用是要制造”余量”：IH 给出 $\sum_{i=1}^k 1/i^2 \le 2 - 1/k$，而我们要证的是 $\le 2 - \frac{1}{k+1}$。两者之差 $-\frac1k$ 与 $-\frac{1}{k+1}$ 恰好留下足够的空间容纳新增的 $+\frac{1}{(k+1)^2}$。

逐步推导：

1. 基础情形 $(n = 1)$：左边 $= \displaystyle\sum_{i=1}^{1} \frac{1}{i^2} = 1$；右边 $= 2 - \frac11 = 1$。故 $1 \le 1$ ✓。
2. 归纳假设 (IH)：假设 $\displaystyle\sum_{i=1}^{k} \frac{1}{i^2} \le 2 - \frac{1}{k}$。
3. 归纳步骤：由 IH， \(\sum_{i=1}^{k+1} \frac{1}{i^2} = \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2} \le \left(2 - \frac{1}{k}\right) + \frac{1}{(k+1)^2} = 2 - \frac{1}{k} + \frac{1}{(k+1)^2}.\) 于是要证目标 $2 - \frac{1}{k+1}$，只需证 \(2 - \frac{1}{k} + \frac{1}{(k+1)^2} \le 2 - \frac{1}{k+1}. \tag{$\\star$}\) 下面完成这个代数验证（官方留作练习）： \(\begin{aligned} (\star) &\iff -\frac{1}{k} + \frac{1}{(k+1)^2} \le -\frac{1}{k+1} & &(\text{两边同时减去 } 2)\\ &\iff \frac{1}{k+1} + \frac{1}{(k+1)^2} \le \frac{1}{k} & &(\text{移项})\\ &\iff \frac{(k+1) + 1}{(k+1)^2} \le \frac{1}{k} & &(\text{左边通分：}\tfrac{1}{k+1} = \tfrac{k+1}{(k+1)^2})\\ &\iff \frac{k+2}{(k+1)^2} \le \frac{1}{k} & &\\ &\iff k(k+2) \le (k+1)^2 & &(\text{两边同乘正数 } k(k+1)^2 > 0 \text{，不等号方向不变})\\ &\iff k^2 + 2k \le k^2 + 2k + 1 & &(\text{两边展开})\\ &\iff 0 \le 1 & &(\text{恒真}) \end{aligned}\) 最后一行恒成立，故 $(\star)$ 成立，归纳步骤完成。
4. 结论：由归纳法原理，对所有 $n \ge 1$，$\sum_{i=1}^n 1/i^2 \le 2 - 1/n$ 成立。作为推论，$\sum_{i=1}^n 1/i^2 \le 2 - 1/n < 2$，原命题也成立。$\blacksquare$

总代价验算（脚本已核 $k = 1$ 到 $8$）：不等式 $2-\frac1k+\frac{1}{(k+1)^2} \le 2-\frac{1}{k+1}$ 在每一处都成立，等价的移项形式 $\frac1k - \frac{1}{(k+1)^2} \ge \frac{1}{k+1}$ 亦全部成立（例如 $k=8$：左边 $0.112654 \ge$ 右边 $0.111111$ ✓）。注意 $k$ 越小余量越大（$k=1$ 时左边 $0.75$ 远大于右边 $0.5$），“余量随 $n$ 递减但始终为正”正是强化形式 $2 - 1/n$ 被选中的原因。

【证明机制解说】：两个强化范例的机制完全同构：原命题的界太”钝”，无法吸收归纳步骤新增的量；强化后的命题提供一个”恰好够用”的收紧界，把新增量吃掉。 判断是否需要强化、以及该强化成什么形式，靠的是先算几个小规模数值看趋势（范例 A 看到 $1,4,9,16,25$ 认出 $n^2$；范例 B 看到部分和远低于 2，于是尝试带 $1/n$ 的余量）。这个”小规模计算 → 发现结构 → 强化命题“的工作流是数学研究中的真实做法，不是考试技巧。

五、简单归纳 vs. 强归纳：两个必证定理

定理 3.6（官方 Note 4 的 Theorem 4.6 / Postage Stamp Problem）：对每个自然数 $n \ge 12$，存在 $x, y \in \mathbb{N}$ 使 $n = 4x + 5y$。

背景：这就是邮票问题 (Postage Stamp Problem)——用 4 分和 5 分两种邮票，支付任意 $\ge 12$ 分的邮资。它也等价于硬币找零问题。

证明策略：用强归纳法，并且需要四个基础情形。为什么必须强归纳？因为归纳步骤里 $k+1$ 要回退到 $(k+1)-4 = k-3$，这不是 $k$，简单归纳假设（只有 $P(k)$）完全帮不上忙。为什么需要四个基础情形？因为归纳步骤对 $k+1 \ge 16$ 才有效（要求回退目标 $\ge 12$），所以 $n = 12, 13, 14, 15$ 这”前四个”必须手工验证，归纳链条从这里起步。

逐步推导：

1. 基础情形 $(n = 12)$：$12 = 4 \cdot 3 + 5 \cdot 0$，取 $(x,y) = (3,0)$ ✓。
2. 基础情形 $(n = 13)$：$13 = 4 \cdot 2 + 5 \cdot 1$，取 $(x,y) = (2,1)$ ✓。
3. 基础情形 $(n = 14)$：$14 = 4 \cdot 1 + 5 \cdot 2$，取 $(x,y) = (1,2)$ ✓。
4. 基础情形 $(n = 15)$：$15 = 4 \cdot 0 + 5 \cdot 3$，取 $(x,y) = (0,3)$ ✓。
5. 归纳假设 (IH，强归纳)：固定任意 $k \ge 15$，假设命题对所有满足 $12 \le n \le k$ 的 $n$ 都已成立。（注意这里假设的是一整段区间，而不只是单个 $k$。）
6. 归纳步骤：证明 $n = k+1$ 的情形。因为 $k \ge 15$，故 $k+1 \ge 16$，从而 $(k+1) - 4 = k - 3 \ge 12$。 于是 $k-3$ 落在归纳假设的覆盖范围 $[12, k]$ 内（它 $\ge 12$ 且 $\le k$），由 IH 存在 $x^{\prime}, y^{\prime} \in \mathbb{N}$ 使 \(k - 3 = (k+1) - 4 = 4x^{\prime} + 5y^{\prime}.\) 两边同时加 4： \(k + 1 = 4x^{\prime} + 5y^{\prime} + 4 = 4(x^{\prime}+1) + 5y^{\prime}.\) 取 $x = x^{\prime} + 1 \in \mathbb{N}$，$y = y^{\prime} \in \mathbb{N}$，即得 $k+1 = 4x + 5y$，$P(k+1)$ 成立。
7. 结论：由强归纳法原理，对所有 $n \ge 12$，存在 $x,y \in \mathbb{N}$ 使 $n = 4x+5y$。$\blacksquare$

【证明机制解说】：这个证明有两个机制要点。

第一，为什么必须强归纳。 归纳步骤唯一可用的回退路径是”给 $n$ 减 4”（因为要凑出一个 4 分邮票）。$n = k+1$ 时回退到 $k-3$。简单归纳只给你 $P(k)$——它说的是 $k$ 能被表示，而 $k$ 与 $k-3$ 之间没有直接的加减 4 关系（$k - (k-3) = 3 \ne 4$），因此 $P(k)$ 完全无用。强归纳假设覆盖了整段 $[12,k]$，$k-3$ 就在其中。判据很清晰：归纳步骤回退的距离不是 1 时，就该用强归纳。

第二，为什么恰好是 4 个基础情形。 归纳步骤的适用条件是”回退目标 $\ge 12$”，即 $n - 4 \ge 12 \iff n \ge 16$。所以 $n=12,13,14,15$ 无法由归纳步骤得到，必须作为基础情形手工验证（四个都恰好需要）。这也解释了为什么门槛偏偏是 12 而不是别的：$12,13,14,15$ 这四连整数恰好能被 $4,5$ 表示，而它们的共同点是”$n \bmod 4$ 取遍 $0,1,2,3$”——见下表。若把门槛降到 11，$n = 11$ 只有 $11 = 4+7$（7 不是 5 的倍数）、$11 = 8+3$、$11 = 11$ 这三种拆法，都失败，故 11 不可表示。所以 $12$ 是最小可行门槛。

算例验算（$n = 12$ 到 $20$，脚本已核）：

由证明直接得到一个算法与一个上界：定理 3.6 的证明过程本身就是构造性算法——”反复给 $n$ 减 4，直到落在 $\{12,13,14,15\}$，套用对应的基础解，然后每减一次 4 就给 $x$ 加 1”。由于最终落点的 $y$ 值最多是 3（$n=15$ 时 $y=3$），而 $x$ 的累加不影响 $y$，故该算法使用的 5 分邮票数永远不会超过 3 张。脚本对 $n = 12$ 到 $200$ 全量验证：最大 $y = 3$（出现在 $n=15$），且每个 $n$ 的表示都正确 ✓。

定理 3.7（官方 Note 4 的 Theorem 4.7）：每个自然数 $n > 1$ 都可写成一个或多个质数之积。

证明策略：用强归纳法，归纳变量 $n$，起始于 $n = 2$。归纳步骤需要分情形（$k+1$ 是质数 / 不是质数）。为什么必须强归纳？当 $k+1$ 是合数时，它可以写成 $k+1 = xy$，其中 $x, y$ 都远小于 $k+1$（例如 $42 = 6 \times 7$）。我们要用到 $P(6)$ 和 $P(7)$，而 $P(7)$ 根本不是 $P(k)$（这里 $k=41$，$P(41)$ 是”41 是质数”）——简单归纳提供的假设对此毫无帮助。

逐步推导：

记 $P(n)$ 为命题”$n$ 可以写成质数之积”。证明对所有 $n \ge 2$ 成立。

1. 基础情形 $(n = 2)$：$2$ 本身是质数，故它是”一个质数之积”（乘积中只有一项）。$P(2)$ 成立 ✓。（注意：这里”一个或多个质数”允许只有一项，正是为了容纳质数本身。）
2. 归纳假设 (IH，强归纳)：假设 $P(n)$ 对所有 $2 \le n \le k$ 成立（$k \ge 2$）。
3. 归纳步骤：证明 $P(k+1)$，即 $k+1$ 可写成质数之积。分两种情形（穷尽且互斥：按质数定义，$k+1$ 要么是质数，要么不是）：
   • 情形 1：$k+1$ 是质数。则 $k+1$ 本身就是”一个质数之积”，取乘积只含一项即可。$P(k+1)$ 成立 ✓。
   • 情形 2：$k+1$ 不是质数。按合数的定义，存在正整数 $x, y$ 满足 \(k+1 = xy, \qquad 1 < x, y < k+1.\) 由于 $x, y < k+1$ 且都 $> 1$，故 $2 \le x \le k$ 且 $2 \le y \le k$——两者都落在归纳假设的覆盖范围内。 由 IH，$x$ 可写成质数之积 $x = q_1 q_2 \cdots q_s$，$y$ 可写成质数之积 $y = r_1 r_2 \cdots r_t$（各 $q_i, r_j$ 都是质数）。 于是 \(k+1 = xy = q_1 q_2 \cdots q_s \cdot r_1 r_2 \cdots r_t,\) 即 $k+1$ 也是质数之积。$P(k+1)$ 成立 ✓。
4. 结论：由强归纳法原理，每个 $n > 1$ 都可写成质数之积。$\blacksquare$

【证明机制解说】：这个证明的机制是”分情形 + 强归纳的配合”。分情形把”最坏的情况”隔离出来：情形 1（$k+1$ 质数）是一步收口的平凡情形；情形 2（合数）才是需要归纳假设的地方。而强归纳的必要性在情形 2 暴露无遗——分解出的 $x, y$ 是任意的小于 $k+1$ 的数，不是 $k$。看官方给的例子：$k+1 = 42 = 6 \times 7$，此时我们要用 $P(6)$ 与 $P(7)$，而简单归纳在 $k=41$ 时只允许假设 $P(41)$ 成立——”41 是质数”这条信息对分解 42 毫无用处。

算例验算（脚本已核）：

顺带补上 L02 的欠账：定理 3.7 直接蕴含 L02 里被借用的引理”每个大于 1 的自然数要么是质数，要么有质因子”——若 $n$ 是质数则前半成立；若 $n$ 不是质数，定理 3.7 给出 $n = q_1\cdots q_s$（$s \ge 2$），取 $q_1$ 即为 $n$ 的质因子。这就是 L02 的 Euclid 证明所依赖的那个引理的正式来源。

六、强归纳的第三个应用：递归程序正确性（二分查找）

背景：findWord(W, D) 在字典 $D$ 中查找单词 $W$。若 $D$ 只有 1 页，直接暴力查找；否则取出中间页的第一个词 $W^{\prime}$：若 $W$ 排在 $W^{\prime}$ 之前，递归到前半本，否则递归到后半本。（$D$ 有偶数 $2m$ 页时，定义中间页为第 $m+1$ 页，从而两个半本都严格小于原尺寸。）

findWord(W, D):
    前置条件: W 是单词, D 是字典的子集且至少有 1 页
    后置条件: 返回 W 的定义, 或返回 "W not found"

    if (D 恰好有 1 页):                     # 基础情形
        在 D 上暴力查找 W
        若找到, 返回其定义; 否则返回 "W not found"

    // 递归情形
    W' = D 的中间页上的第一个单词
    if (W 排在 W' 之前):
        return findWord(W, D 的前半本)
    else:
        return findWord(W, D 的后半本)

定理 3.8（官方 Note 4 §4 Example 2）：findWord() 是正确的，即若 $W$ 在 $D$ 中，它返回 $W$ 的定义；若 $W$ 不在 $D$ 中，它返回”W not found”。

证明策略：用强归纳法，对 $D$ 的页数 $n$ 做归纳。

为什么必须用强归纳？ 因为递归调用的参数不是 $n-1$，而是两个半本之一的页数，它可能是 $\lceil n/2 \rceil$ 或 $\lfloor n/2 \rfloor$——远小于 $n$，且与 $n-1$ 无关。简单归纳的 $P(k)$ 只覆盖 $n = k$，无法为”$n-1$ 页的半本”或更小的半本背书。（脚本验算：1000 页的字典只需 10 次折半就到 1 页，可见递归深度远小于 $n$——这正是强归纳必需、而简单归纳力所不及的直接体现。）

逐步推导：

1. 基础情形 $(n = 1)$：若 $D$ 只有 1 页，算法走基础分支，在该页上暴力查找 $W$。$W$ 若在 $D$ 中则必然在这一页上，被找到并返回定义；若不在，则返回”W not found”。与后置条件完全一致 ✓。
2. 归纳假设 (IH，强归纳)：假设 findWord() 对所有页数 $1 \le n \le k$ 的输入都是正确的。
3. 归纳步骤：证明页数 $n = k+1$ 时正确。此时 $k+1 \ge 2$，算法不走基础分支，而是算出中间页的第一个词 $W^{\prime}$。
   • 因字典按字典序排列，比较 $W$ 与 $W^{\prime}$ 就能判定 $W$ 可能在哪一半：若 $W < W^{\prime}$，则 $W$ 只可能在前半本；否则 $W$ 只可能在后半本（这一步的正确性依赖字典已排序这一前提，属于前置条件）。
   • 算法在相应的半本上递归调用。按中间页的定义（偶数页取第 $m+1$ 页），两个半本的页数都 $\le \lceil (k+1)/2 \rceil \le k$（对 $k \ge 1$）——严格小于 $k+1$，故落在归纳假设的覆盖区间 $[1,k]$ 内。
   • 由 IH，该递归调用返回正确答案（找到定义，或报告未找到）。
   • 算法直接 return 该递归调用的返回值，因此 $n = k+1$ 时输出也正确。
4. 结论：由强归纳法原理，findWord() 对所有页数都正确。$\blacksquare$

【证明机制解说】：这是归纳法用于程序正确性证明的模板，值得记住其结构：

• 基础情形 对应程序的递归基 (base case) / 终止分支。
• 归纳假设 对应”递归调用返回正确结果“这一信任声明——在证明里我们不需要展开递归调用的内部执行过程，只需引用 IH。
• 归纳步骤 对应”把子问题的正确性组合成原问题的正确性“，即除了递归调用之外的所有代码路径。
• 良序原理 保证递归必然终止（页数严格递减，不可能无限下降），因此”信任递归调用”不是循环论证。

用这个模板去读任何递归算法的正确性证明，结构都是一样的：找到衡量问题规模的量（这里是页数 $n$）→ 证明每次递归该量严格减小 → 对基础情形验证 → 用 IH 处理递归调用 → 把返回值组装成答案。

七、递归与归纳：Fibonacci 数列

定义（Fibonacci 数列）：递归定义为 \(F(0) = 0, \qquad F(1) = 1, \qquad F(n) = F(n-1) + F(n-2) \quad (n \ge 2).\)

直观来源（Fibonacci 的兔子问题，1202 年）：从一对兔子开始，每个月每对成年兔生一对新兔，新生兔从第二个月起具备生育能力。设 $F(n)$ 为第 $n$ 个月的兔子对数。第 $n$ 个月时，能生育的是上个月就已经存在的 $F(n-2)$ 对，它们各生一对新兔，故新增 $F(n-2)$ 对；加上原有的 $F(n-1)$ 对，得 $F(n) = F(n-1) + F(n-2)$。

算例验算（脚本已核）：

（比值 $F(13)/F(12) = 1.618056$，逼近黄金比 $\phi = 1.618034$；真实增长率约为 $\phi^n$。）

命题（官方练习）：$F(n) \ge 2^{(n-1)/2}$ 对所有 $n \ge 3$ 成立。（这给出指数增长的一个下界。）

为什么需要两个基础情形：归纳步骤要用 $F(k+1) = F(k) + F(k-1)$，同时需要 $P(k)$ 与 $P(k-1)$。取 $k = 3$ 时要 $P(2)$——但 $P(2)$ 不成立（$F(2) = 1 < 2^{1/2} \approx 1.414$）。所以必须从 $n=3$ 和 $n=4$ 两个基础情形起步，让归纳步骤覆盖 $k \ge 4$。

证明：

1. 基础情形 $(n=3)$：$F(3) = 2 \ge 2^{(3-1)/2} = 2^1 = 2$ ✓。
2. 基础情形 $(n=4)$：$F(4) = 3 \ge 2^{(4-1)/2} = 2^{1.5} \approx 2.828$ ✓。
3. 归纳假设：假设对 $k$ 和 $k-1$（$k \ge 4$）有 $F(k) \ge 2^{(k-1)/2}$ 与 $F(k-1) \ge 2^{(k-2)/2}$。
4. 归纳步骤： \(F(k+1) = F(k) + F(k-1) \ge 2^{(k-1)/2} + 2^{(k-2)/2} = 2^{(k-2)/2}\left(2^{1/2} + 1\right) > 2^{(k-2)/2} \cdot 2 = 2^{k/2} = 2^{((k+1)-1)/2}.\) 故 $P(k+1)$ 成立。（关键不等式是 $2^{1/2} + 1 \approx 2.414 > 2$。）
5. 结论：$F(n) \ge 2^{(n-1)/2}$ 对所有 $n \ge 3$ 成立 ✓。

脚本验算：$n = 3$ 到 $15$ 全部满足（如 $n=10$：$55 \ge 22.627$ ✓）。中间不等式的数值：$2^{(k-2)/2} + 2^{(k-3)/2} \ge 2^{(k-1)/2}$ 在 $k=5$ 到 $12$ 上全部成立（例如 $k=8$：$13.657 \ge 11.314$ ✓）。

递归实现与效率

// 版本一：直接照抄递归定义
function F(n):
    if n = 0 then return 0
    if n = 1 then return 1
    else return F(n-1) + F(n-2)

// 版本二：迭代（把尾递归改成循环）
function F2(n):
    if n = 0 then return 0
    if n = 1 then return 1
    a = 1
    b = 0
    for k = 2 to n do:
        temp = a
        a = a + b
        b = temp
    return a

版本一的调用次数（脚本已核）：

可以看到调用次数超过 $F(n)$（例如 $n=10$ 时 $177 > 55$），几乎呈指数增长——用归纳可以证明调用次数 $\ge F(n)$。这是”重复子问题被反复重算”的经典例子。版本二只需 $n-1$ 次循环迭代，是线性时间：a, b 始终保存相邻两个 Fibonacci 数，循环不变式”第 $k$ 轮结束时 $(b,a) = (F(k-1), F(k))$”可用归纳证明，从而 $F_2(n) = F(n)$。

这正是归纳法与编程的分工：递归定义了”是什么”，归纳法证明了”为什么对”。 迭代版本的循环不变式、递归版本的调用次数下界、以及”$F_2 = F$”的等价性，全都靠归纳法。

与经典问题的联系

（一）归纳法 → 算法正确性证明（贯穿 L05–L11）

本讲 §六 的 findWord 证明给出了”归纳证明递归程序”的完整模板。它在后续讲次中的直接复用：

• L05 Euclid 算法：证明 $\gcd(a,b)$ 在递归调用中保持不变（用归纳），并证明算法终止（余数严格递减，$b$ 每次变小，由良序原理终止）。
• L06 RSA 解密正确性：证明 $m^{ed} \equiv m \pmod N$，其中要用到”快速幂 (fast exponentiation)”的归纳正确性与 FLT/CRT。
• L08 Berlekamp–Welch 纠错解码：证明在错误数 $\le e$ 时解码唯一，归纳结构出现在”多项式次数与根的个数”的计数中。
• L11 Gale–Shapley 稳定匹配：证明算法终止（每轮至少一次求婚不可重复，求婚总数有上界 $n^2$）与输出稳定（分情形证明没有阻塞对）。

（二）强归纳 → 唯一分解与数论基础（L04–L05）

定理 3.7（质数分解存在性）是算术基本定理的一半。有了它，L04 的模运算、L05 的欧几里得算法与费马小定理才能建立在稳固的整数结构之上。请注意它的证明策略值得反复体会：“存在性”用强归纳（把 $n$ 拆成更小的 $a,b$），”唯一性”则要靠 Euclid 引理（$p \mid ab \Rightarrow p\mid a$ 或 $p \mid b$，其证明需要 L05 的 Bézout 等式）。本讲只给出存在性，唯一性要到 L05 才补齐。

（三）鸽笼 + 归纳 → 组合计数与概率（L14–L20）

• L14 计数：二项式系数 $\binom{n}{k}$ 的 Pascal 递推 $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ 正是”归纳式”的，二项式定理的证明就是一次归纳。
• L20 期望线性性：$\mathbb{E}\!\left[\sum X_i\right] = \sum \mathbb{E}[X_i]$ 对任意有限个随机变量成立，标准证法是对变量个数 $n$ 做归纳。
• L20 哈希与负载均衡：与 L02 的鸽笼原理衔接——鸽笼给出”冲突必然存在”的确定性结论，而负载均衡分析给出”每个桶的期望负载 $= n/k$”的概率刻画。

（四）强化归纳假设 → 一般化的数学研究技能

“先算小规模、发现结构、证明强化命题”这个工作流在后面反复出现：

• L23 集中不等式：切尔诺夫界 (Chernoff bound) 的推导先证一个带有可调参数 $t$ 的更强界（moment generating function 版本），再优化 $t$ 得到最终形式——这就是”强化以获得自由度”的典型。
• L26 马尔可夫链：稳态分布的存在性证明中，常常需要把”收敛”强化为”带速率的收敛”（几何收敛），否则归纳步骤无法推进。

与其他讲次的关联

• 与 L00–L02（证明工具箱）：归纳法把前四讲的所有技巧全部打包进归纳步骤。本讲定理 3.2 的归纳步骤是一次代数直接证明；定理 3.3（两色定理）的归纳步骤是一次分情形证明（情形 1/情形 2）；定理 3.7 的归纳步骤也是分情形；而”归纳法合法性”的论证（良序原理那段）本身是一次反证法。所以归纳法不是第五种孤立技巧，而是”用一个有限证明封装无穷多个证明”的元技巧。
• 与 L01（命题逻辑）：归纳法依赖 L01 的全称量词 $\forall$ 与蕴含 $\Rightarrow$ 的精确语义。”$P(k) \Rightarrow P(k+1)$ 对任意 $k$” 中的”任意”必须理解为全称量词，否则就会出现”漏掉 $k=1$”这类漏洞（见下节”所有马同色”的分析）。此外，定理 3.7 归纳步骤的两种情形互斥穷尽，其合法性来自 $P \vee \neg P$（排中律）。
• 与 L02（逆否/反证/分情形）：良序原理证明归纳法合法性的那段论证，本质上是反证法 + 取最小反例。而 L02 借用的引理”每个 $n>1$ 要么是质数要么有质因子”，在本讲定理 3.7 处被正式证明并偿还——注意这个依赖方向：L02 的定理 2.4（质数无穷多）在逻辑上依赖 L03 的定理 3.7。这在课程安排上是完全正常的，但你自己写证明时要清楚”我引用了哪个还没证的结果”。
• 与 L04（模运算）：定理 3.2 的”$3 \mid n^3-n$”在 L04 会被重述为 $n^3 \equiv n \pmod 3$，并能用费马小定理（L05）的 $n^p \equiv n \pmod p$ 一步得到（取 $p=3$）。同一命题在更高层的工具下会变得平凡——这是学习数学的一条重要经验。
• 与 L09–L10（图论、树与平面图）：树的性质 $\vert E\vert = \vert V\vert - 1$、握手引理 $\sum_v \deg(v) = 2\vert E\vert $、平面图的欧拉公式 $V - E + F = 2$ 全部用归纳法证明，且都是”删一个顶点/边然后修补”的模式——与本讲定理 3.3 的两色定理证明机制完全相同。
• 与 L12–L13（可数性、可计算性）：L12 中”每个自然数都能被某个图灵机编码”的论证、L13 中”程序与输入配对枚举”的构造，都依赖自然数的良序性与编码的归纳性质。

关键要点

1. 归纳法三件套 + 多米诺模板：

  P(0)                P(k) => P(k+1)              结论: 全部倒下
   |                        |                            |
   v                        v                            v
 +---+  +---+  +---+  +---+  +---+  +---+        推倒第0张 (基础情形)
 | P0|  | P1|  | P2|  | P3|  |...|  | Pn|        牌距够近 (归纳步骤)
 +---+  +---+  +---+  +---+  +---+  +---+
   ^      ^      ^      ^
   |      |      |      |
  推倒   被撞倒 被撞倒 被撞倒  ......  连锁反应覆盖所有 n

 必须同时具备：
 (A) 基础情形：P(0) 成立          —— 否则一张都不倒
 (B) 归纳步骤：forall k, P(k)=>P(k+1) —— 否则链条断在 k 处
 (C) 良序原理：保证不存在"反例集合的最小元" —— 合法性的终极依据

1. 证明骨架模板（照这个格式写，阅卷不会扣分）：

 定理: forall n >= n0, P(n).
 证明: 我们对 n 做 [简单/强] 归纳.
   Base Case (n = n0):  [逐一验证 P(n0) 成立, 写出两边相等]
                       [若需多个基础情形, 全部列出: n0, n0+1, ...]
   Induction Hypothesis: 假设对任意 k >= n0, P(k) 成立.
                       [强归纳: 假设 P(n0),...,P(k) 全部成立.]
   Inductive Step: 证明 P(k+1).
                       [关键动作: 把 P(k+1) 的目标式拆成
                        "IH 能处理的部分" + "剩下的部分"]
                       [注明在哪一步用了 IH]
                       [若回退距离 != 1, 改用强归纳; 若需拆分情况, 显式声明
                        "以下情形穷尽且互斥"]
                       [收口: 得出 P(k+1) 成立]
   Conclusion: 由 [强] 归纳法原理, forall n >= n0, P(n).  QED

1. 基础情形不是形式主义。漏掉基础情形会证出”所有马颜色相同”这样的荒谬结论；而基础情形的个数由归纳步骤的适用门槛决定（定理 3.6 需要四个，Fibonacci 下界需要两个）。

2. 归纳步骤回退距离 $\ne 1$ 时必须用强归纳。判据：如果你在归纳步骤里要用 $P(k-3)$、$P(x)$（$x$ 远小于 $k$）、或两个半本的 $P$，就换成”假设 $P(n_0),\dots,P(k)$ 全部成立”。强归纳与简单归纳证明能力等价，只是更好用。

3. 归纳假设太弱时，去证一个更强的命题。信号是”归纳步骤卡住、缺少关于 $k$ 的精确信息”。强化前先手算 $n = 1,2,3,4,5$ 的值，观察结构（范例 A 由 $1,4,9,16,25$ 认出 $n^2$；范例 B 由部分和远小于 2 想到带 $1/n$ 的余量）。

4. 归纳法 = 递归的数学影子。递归定义靠良序原理保证良定义；递归程序的正确性证明结构是”基础情形 $\leftrightarrow$ 递归基、IH $\leftrightarrow$ 信任递归调用、归纳步骤 $\leftrightarrow$ 组装返回值”。归纳法就是”分治 (divide and conquer)”正确性的语言。

常见误区与注意事项

误区 1（本讲头号陷阱）：”所有马颜色相同”——归纳步骤在 $n=1$ 处失效

这是 Pólya 流传下来的经典伪证，也是 CS70 最著名的归纳法陷阱。

Theorem（伪）：所有的马都是同一种颜色。 “证明”：对马的数量 $n$ 做归纳。记 $P(n)$ 为”任意 $n$ 匹马都是同一种颜色”。 基础情形 $(n=1)$：一匹马显然是同一种颜色 ✓。 归纳假设：假设 $P(n)$ 对某个 $n \ge 1$ 成立。 归纳步骤：考虑 $n+1$ 匹马 $\{h_1, h_2, \dots, h_{n+1}\}$。把最后一匹排除，对前 $n$ 匹 $\{h_1,\dots,h_n\}$ 用归纳假设，得出它们同色。同理，对后 $n$ 匹 $\{h_2,\dots,h_{n+1}\}$ 用归纳假设，得出它们也同色。这两组的”中间马”$\{h_2,\dots,h_n\}$ 属于两个集合的交集，因此它们既与 $h_1$ 同色、又与 $h_{n+1}$ 同色，故全部 $n+1$ 匹马同色。由归纳法原理，所有马同色。$\spadesuit$

错在哪：归纳步骤声称证明的是 $\forall n \ge 1,\ P(n) \Rightarrow P(n+1)$。但这个蕴含式对 $n = 1$ 是假的。

仔细看 $n = 1$ 时的情形：要证 $P(2)$，即两匹马 $\{h_1, h_2\}$ 同色。按”证明”的做法：

• 前 $n = 1$ 匹是 $\{h_1\}$ —— 由 $P(1)$ 得出”$\{h_1\}$ 中所有马同色”✓（这句话是空洞真 (vacuously true) 的，一匹马当然与自己同色）。
• 后 $n = 1$ 匹是 $\{h_2\}$ —— 由 $P(1)$ 得出”$\{h_2\}$ 中所有马同色”✓（同样空洞）。
• 关键一步：“中间马” $\{h_2,\dots,h_n\} = \{h_2,\dots,h_1\} = \varnothing$，交集是空的！

空交集里没有任何一匹马，所以无法把 $h_1$ 的颜色传递给 $h_2$。整个论证依赖”存在一匹同时属于两个集合的马”作为颜色传递的桥梁，而 $n=1$ 时这座桥不存在。

脚本验算交集大小：$\{h_1,\dots,h_n\} \cap \{h_2,\dots,h_{n+1}\} = \{h_2,\dots,h_n\}$，元素个数为 $\max(0, n-1)$。

所以正确的诊断是：基础情形 $P(1)$ 是真的，$n \ge 2$ 时的归纳步骤也是真的，唯独 $P(1) \Rightarrow P(2)$ 这一步是假的。 归纳链条从第 1 格到第 2 格就断了，所以 $P(2)$ 从未被建立，$P(3)$ 起全部落空。

从这个陷阱学到的三条教训：

1. 归纳步骤必须对”每一个” $k$ 成立。写成 $\forall k \ge 1,\ P(k)\Rightarrow P(k+1)$——只要有一个 $k$ 失效，整个链条就断。检查时要把最小的那个 $k$ 单独拿出来想清楚。
2. “空洞真”是小规模情形的常见伪装。$P(1)$ 的成立毫不费力（一匹马自比），恰恰因为它是空的，它不携带任何可用于 $n=2$ 的信息。
3. 修补方案：如果归纳步骤对 $n \ge 2$ 才有效，必须把基础情形补到 $n=2$（即手工验证”两匹马同色”）——但这一步显然做不到（两匹马可以颜色不同），所以正确的结论是这个定理本身为假，而不是证明写法需要修补。这个区分很重要：有些时候是证明错了，有些时候是命题错了。

误区 2：只证归纳步骤，不证基础情形

漏掉基础情形的后果不是”证明不完整”，而是归纳链条根本没有起点。用”所有马同色”的例子做思想实验：即使归纳步骤完全正确，若从 $n=1$ 起就不验证，$P(1)$ 无从建立，$P(2), P(3), \dots$ 全部无法推出。用多米诺的话说：牌距排得再完美，没有第一推，一张都不会倒。考试里漏写基础情形是标准的扣分点。

误区 3：把归纳假设当成已证事实，或反过来”重复证明”

• 错误写法：”归纳假设：对任意 $k$，$P(k)$ 成立。” —— 这是把要证的东西直接假设了（循环论证）。正确写法必须强调 $k$ 是任意的但固定的一个值：”假设对某个任意的 $k \ge 0$，$P(k)$ 成立。”
• 另一种错误：在归纳步骤里重新从头证明 $P(k)$。归纳假设是给定的，不需要证明，只需要使用。

误区 4：该用强归纳时用了简单归纳

定理 3.6 若用简单归纳：归纳假设只有 $P(k)$，要说”$k+1 = k - 3 + 4$”，可 $P(k)$ 说的是 $k$ 能被表示，与 $k-3$ 无关，论证完全断掉。定理 3.7 若用简单归纳：$42 = 6 \times 7$ 需要 $P(6)$ 与 $P(7)$，而 $k = 41$ 时简单归纳只给 $P(41)$（”41 是质数”），毫无帮助。findWord 若用简单归纳：递归调用的参数是两个半本的页数（可能远小于 $k$），$P(k)$ 覆盖不到。

判据（重复一遍）：归纳步骤需要的回退目标不是 $k$ 本身时，就必须用强归纳。

误区 5：基础情形的个数想当然

三种典型误判：

• 该多反而少：定理 3.6 需要 4 个基础情形（$12,13,14,15$），因为归纳步骤只在 $n \ge 16$ 时可用。Fibonacci 下界需要 2 个（$n=3,4$），因为归纳步骤要用 $P(k)$ 与 $P(k-1)$ 两条假设，起点必须给足两条。
• 该少反而多：写了不必要的基础情形不算错，但会浪费时间、且可能掩盖”归纳步骤其实覆盖了它”这个事实。
• 判据：看归纳步骤的适用门槛。归纳步骤要求”回退目标 $\ge$ 某阈值”时，阈值到第一次能用归纳步骤的那个数之间全部都要手工验证。

误区 6：归纳变量选错

“对 $n$ 做归纳”里的 $n$ 必须是命题中那个会变化的、且所有量都能向它归约的参数。例如证明”$n$ 条直线把平面分成 $n(n+1)/2+1$ 个区域”时，归纳变量应是直线数，不是区域数、也不是交点数。选错变量的典型症状是：归纳步骤里发现”$k+1$ 的情形”与”$k$ 的情形”之间找不到构造性联系。

误区 7：把”验证前几项”当成证明

本讲的 $n^2-n+41$ 是最有力的警告：它连续 41 个值（$n = 0$ 到 $40$）都是质数，$n=41$ 时崩溃。任何有限次验证都不能排除无穷多个情形中的反例。 归纳法之所以必要，就是它用一个有限论证（两步）覆盖了无穷多情形。反过来说——如果你只打算验证有限个 $n$，那就不叫证明，叫测试（这也正是 L13 停机问题、L12 可数性所强调的”有限手段 vs 无穷对象”主题的雏形）。

误区 8：在归纳步骤中悄悄改变了命题

强化归纳假设是合法且常用的技巧（本讲定理 3.4、3.5），但必须做到两点：(i) 明确写出强化后的命题 $P^{\prime}(n)$，并说明 $P^{\prime}(n) \Rightarrow P(n)$；(ii) 基础情形与归纳步骤都是针对 $P^{\prime}$ 的。常见错误是”归纳假设用了强化版，结论却写回原版”，导致归纳步骤证的不是同一个命题——这在逻辑上等同于把归纳链条中途换掉了。

思考题（带答案）

Q1.（纯计算） 用归纳法验证下列数值事实，并写出对应的公式。

(a) 计算 $1^2 + 2^2 + \cdots + n^2$ 在 $n = 1,2,3,4,5$ 的值，验证公式 $\frac{1}{6}n(n+1)(2n+1)$。 (b) 计算 $F(10)$ 与递归版本 F(10) 的调用次数，验证”调用次数 $\ge F(n)$”。 (c) 验证 $n = 12$ 到 $20$ 每一个都能写成 $4x+5y$，并给出每种表示。

Q2.（概念理解） 判断下列说法是否正确，并说明理由。

(a) 强归纳法能证明一些简单归纳法无法证明的命题。 (b) 定理 3.6（$n \ge 12$ 可写成 $4x+5y$）可以用简单归纳法证明，只要把基础情形从 1 个改成 4 个。 (c) 在”所有马同色”的伪证中，错误出在基础情形 $P(1)$ 上。 (d) 用归纳法证明 $\forall n \ge 1$：前 $n$ 个奇数之和是完全平方数时，”强化归纳假设”意味着我们证明了一个更强的命题，所以这个证明比原命题难。

Q3.（证明能力） 用强归纳法证明：每个大于 1 的自然数要么是质数，要么有质因子。

（提示：这是 L02 的 Euclid 证明所借用的引理，请把它的正式证明补上，并指出它与定理 3.7 的关系。）