• https://www.eecs70.org/assets/pdf/notes/n3.pdf
• 小测验

离散数学与程序设计精讲：数学归纳法（Mathematical Induction）

一、 基础数学归纳法（Simple Mathematical Induction）

1.1 起：直观引入与递归的联想

在 UC Berkeley 的 CS 61A 课程中，我们深入学习了递归（Recursion）的思想：将一个大问题拆解为一个或多个与原问题相似但规模更小的子问题，并通过建立基准情况（Base Case）来防止无限循环。

数学归纳法（Mathematical Induction）*在逻辑结构上与递归有着惊人的相似性。它是一种强有力的数学证明工具，用于证明某个命题对于所有的自然数* $n \in \mathbb{N}$*（或某一范围内的所有整数）都成立。 我们可以将数学归纳法形象地比喻为*多米诺骨牌：

• 推动第一块骨牌（Base Case）。
• 确保如果第 $k$ 块骨牌倒下，它一定会顺势砸倒第 $k+1$ 块骨牌（Inductive Step）。
• 只要这两个条件满足，整条由无限块骨牌组成的链条就会依次全部倒下。

1.2 承：数学归纳法的标准步骤

要完整地执行一个数学归纳法证明，必须严格遵循以下三个步骤：

1. 基准情况（Base Case）：证明命题在最小的初始值 $n = b$（通常是 $n=0$ 或 $n=1$）时成立。即证明 $P(b)$ 为真。
2. 归纳假设（Induction Hypothesis, IH）：设对任意一个任意但固定的整数 $k \ge b$，命题 $P(k)$ 成立。
3. 归纳步骤（Inductive Step）：在归纳假设的基础上，证明命题对 $n = k+1$ 也成立。即利用 $P(k)$ 的真实性证明 $P(k+1)$ 为真。

形式化逻辑表示：

$(P(0) \wedge (\forall n \in \mathbb{N})(P(n) \Rightarrow P(n+1))) \equiv (\forall n \in \mathbb{N})(P(n))$

💡 Vitamin 1a 易错辨析：

• 问题： $(P(1) \wedge (\forall n \in \mathbb{N})(P(n) \Rightarrow P(n+1)))$ 是否能推出 $P(0)$ 成立？
• 解答： False。由于基准情况是从 $n=1$ 开始递推的，递推链条只能覆盖 $n \ge 1$ 的所有自然数，它对 $n=0$ 的情况一无所知。

1.3 例题精炼

【例题 1】等差数列求和（Theorem 3.1）

证明：对于所有自然数 $n \in \mathbb{N}$，有：

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

证明过程： 令 $P(n)$ 表示等式 $\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$ 成立。我们对 $n$ 展开归纳：

1. Base Case ($n=0$)： 左边 = $\sum_{i=0}^{0} i = 0$ 右边 = $\frac{0(0+1)}{2} = 0$ 左边 = 右边，$P(0)$ 成立。

2. Induction Hypothesis (IH)： 假设对于任意一个固定的 $k \ge 0$，$P(k)$ 成立，即：

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

3. Inductive Step： 我们需要证明 $P(k+1)$ 成立，即 $\sum_{i=0}^{k+1} i = \frac{(k+1)(k+2)}{2}$。 根据求和的定义，我们将第 $k+1$ 项拆离：

   $\sum_{i=0}^{k+1} i = \left(\sum_{i=0}^{k} i\right) + (k+1)$

   利用归纳假设（IH）替换前 $k$ 项的和：

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

   通分合并同类项：

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

   这正是 $P(k+1)$ 的右端表达式。

因此，根据数学归纳法原理，对任意 $n \in \mathbb{N}$，命题成立。 $\quad \blacksquare$

【例题 2】整除性证明（Theorem 3.2）

证明：对于所有的 $n \in \mathbb{N}$，$n^3 - n$ 均能被 3 整除（记作 $3 \mid (n^3 - n)$）。

证明过程： 令 $P(n)$ 为命题 $3 \mid (n^3 - n)$。

1. Base Case ($n=0$)： $0^3 - 0 = 0$。因为任何非零整数都能整除 0（即 $0 = 3 \times 0$），所以 $P(0)$ 成立。

2. Induction Hypothesis (IH)： 假设对于任意 $k \ge 0$，$P(k)$ 成立。即存在一个整数 $q$，使得：

   $k^3 - k = 3q$

3. Inductive Step： 我们要证明 $P(k+1)$ 成立，即证明 $3 \mid ((k+1)^3 - (k+1))$。 展开并整理表达式：

   $(k+1)^3 - (k+1) = (k^3 + 3k^2 + 3k + 1) - (k - 1)$

   将含有 $k^3 - k$ 的项归拢，与其他项分离：

   $(k+1)^3 - (k+1) = (k^3 - k) + 3k^2 + 3k$

   代入归纳假设（IH） $k^3 - k = 3q$：

   $(k+1)^3 - (k+1) = 3q + 3(k^2 + k) = 3(q + k^2 + k)$

   由于 $q, k \in \mathbb{Z}$，所以 $(q + k^2 + k)$ 也是一个整数。 由此可知，$(k+1)^3 - (k+1)$ 是 3 的倍数，即 $3 \mid ((k+1)^3 - (k+1))$。

因此，根据数学归纳法原理，对任意 $n \in \mathbb{N}$，命题成立。 $\quad \blacksquare$

二、 强化归纳假设（Strengthening the Induction Hypothesis）

2.1 起：为什么要“以退为进”？

在手写笔记中，你提到了一个非常深刻的直观感受：

“通过一个更强的证明，比原来的弱命题证明更加减免。” “让我联想到在《算法导论》（CLRS）中用代入法证明递归式时，证明上下界所使用的方法。”

你的直觉完全正确！ 在《算法导论》的代入法中，如果我们想证明某个递归式 $T(n) = 2T(n/2) + n$ 的上界是 $O(n \log n)$，有时如果直接假设 $T(n) \le c n \log n$，在归纳步骤中可能会因为边界多余常数项而无法闭合。此时，我们往往需要猜测一个更强、更具体的约束条件（例如 $T(n) \le c n \log n - d n$）来抵消多余的项。

这在数学归纳法中被称为“强化归纳假设”。

• 看似矛盾的常识：要证明一个更强的命题，难度应该更大。
• 数学上的真相：较弱的命题包含的信息太少，导致你的归纳假设（IH）*太弱，在 Inductive Step 中无法提供足够的信息来推导* $P(k+1)$*；而一个更具体、结构更紧凑的强命题，能够提供*更具结构性、更有力的归纳假设，从而让递推步骤迎刃而解。

2.2 承：例题对比与深度剖析

【经典例题 1】奇数之和与完全平方数

❌ 失败的尝试（归纳假设过弱）

• 原命题 $P(n)$：前 $n$ 个奇数的和是一个完全平方数（Perfect Square）。

• Base Case ($n=1$)：第 1 个奇数是 1，$1 = 1^2$ 是完全平方数。成立。

• 归纳假设 (IH)：假设前 $k$ 个奇数的和是一个完全平方数，即：

  $\sum_{i=1}^{k} (2i - 1) = m^2 \quad (\text{其中 } m \in \mathbb{Z})$

• 归纳步骤 (Inductive Step)：前 $k+1$ 个奇数的和为：

  $\sum_{i=1}^{k+1} (2i - 1) = \left(\sum_{i=1}^{k} (2i - 1)\right) + (2k+1) = m^2 + 2k + 1$

  卡壳点： 我们只知道 $m^2 + 2k + 1$ 这个表达式，但由于不知道 $m$ 和 $k$ 之间存在什么具体的数量关系，完全无法证明 $m^2 + 2k + 1$ 也是一个完全平方数！ 证明在此处中断。

成功的强化（强化归纳假设）

• 强化后的命题 $Q(n)$：前 $n$ 个奇数的和等于 $n^2$。 （这里我们将抽象的“是完全平方数”强化为了具体的代数式“等于 $n^2$”）

• Base Case ($n=1$)：$1 = 1^2$。成立。

• 归纳假设 (IH)：假设前 $k$ 个奇数的和恰好等于 $k^2$：

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

• 归纳步骤 (Inductive Step)：计算前 $k+1$ 个奇数的和：

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

  代入强归纳假设：

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

  这完美符合了 $Q(k+1)$ 的要求！证明极其丝滑地完成了。 $\quad \blacksquare$

【经典例题 2】倒数平方和的有界性证明（Theorem 3.5 & Vitamin 1a Q2.1）

❌ 失败的尝试

• 原命题：证明对于所有自然数 $n \ge 1$，有 $\sum_{i=1}^{n} \frac{1}{i^2} \le 2$。

• 尝试归纳：假设 $\sum_{i=1}^{k} \frac{1}{i^2} \le 2$。

• 尝试递推：

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

  由于 $\frac{1}{(k+1)^2} > 0$，所以 $2 + \frac{1}{(k+1)^2} > 2$。我们根本无法得出它依然 $\le 2$。归纳失败。

成功的强化（添加修正项）

我们通过引入一个负的修正项 $-\frac{1}{n}$，将命题强化为：

$\sum_{i=1}^{n} \frac{1}{i^2} \le 2 - \frac{1}{n}$

(注：因为 $2 - \frac{1}{n} < 2$，所以只要这个强化命题成立，原命题自然成立。这对应了 Vitamin 1a 中的 Q2.1。)

证明过程：

• Base Case ($n=1$)： 左边 = $1$ 右边 = $2 - \frac{1}{1} = 1$ 左边 $\le$ 右边。成立。

• 归纳假设 (IH)：假设 $n=k$ 时命题成立，即：

  $\sum_{i=1}^{k} \frac{1}{i^2} \le 2 - \frac{1}{k}$

• 归纳步骤 (Inductive Step)： 我们需要证明 $n=k+1$ 时，$\sum_{i=1}^{k+1} \frac{1}{i^2} \le 2 - \frac{1}{k+1}$。 根据定义与归纳假设：

  $\sum_{i=1}^{k+1} \frac{1}{i^2} = \left(\sum_{i=1}^{k} \frac{1}{i^2}\right) + \frac{1}{(k+1)^2} \le 2 - \frac{1}{k} + \frac{1}{(k+1)^2}$

  现在，我们只需要证明：

  $2 - \frac{1}{k} + \frac{1}{(k+1)^2} \le 2 - \frac{1}{k+1}$

  两边同时消去 2，这等价于证明：

  $\frac{1}{(k+1)^2} \le \frac{1}{k} - \frac{1}{k+1}$

  对右边进行通分：

  $\frac{1}{k} - \frac{1}{k+1} = \frac{(k+1) - k}{k(k+1)} = \frac{1}{k(k+1)}$

  显然，由于对所有 $k \ge 1$，有 $k(k+1) < (k+1)^2$，因此其倒数关系成立：

  $\frac{1}{(k+1)^2} < \frac{1}{k(k+1)}$

  由此得证：

  $\sum_{i=1}^{k+1} \frac{1}{i^2} \le 2 - \frac{1}{k+1}$

因此，由数学归纳法原理，强化后的命题成立。由于 $2 - \frac{1}{n} < 2$，原命题 $\sum_{i=1}^{n} \frac{1}{i^2} < 2$ 亦成立。 $\quad \blacksquare$

2.3 总结：寻找“更强命题”的经验法则

你在笔记中提炼出了三个非常宝贵的经验法则：

1. 规律探索法：先动手计算并检查前几个具体的小例子（例如 $n=1, 2, 3, 4$），在脑海中勾勒出可能隐藏的具体数学规律，而不是盲目开始证明。
2. 具象化法：思考是否可以将性质中模糊的“存在性描述”（如“存在某种性质”）提炼并修改为等于某个具体的数学表达式（如将“是完全平方数”具象化为“$= n^2$”）。
3. 修正项调优法：对于不等式的证明，尝试在主项后添加一个动态的负修正项（如 $-\frac{1}{n}$ 或 $-\frac{c}{n}$），利用该修正项在递推时的“消耗”来抵消多余的项。这与算法分析中代入法添加常数项 $d n$ 的思想如出一辙。

三、 强归纳法（Strong Induction）

3.1 核心概念：弱归纳法 vs 强归纳法

你在手写笔记的第三页写道：

“这里的几道证明题我都没看懂，所以我没有体会到强归纳法的优点。” “后面的内容我几乎没怎么看懂。”

别担心！让我们彻底把这个问题讲清楚。

1. 它们在假设上的区别是什么？

• 弱归纳法（Simple/Weak Induction）：
  • IH：假设 $P(k)$ 为真。
  • 任务：仅仅用第 $k$ 块骨牌，去推导第 $k+1$ 块骨牌 $P(k+1)$ 为真。
• 强归纳法（Strong Induction）：
  • IH：假设 从初始状态到 $k$ 的所有命题全都是真的。即 $P(\text{base case}), \dots, P(k)$ 全部为真。
  • 任务：利用这一整包已知为真的命题，去共同推导 $P(k+1)$ 为真。

2. 强归纳法是不是比弱归纳法更强大？

不是。 在数学逻辑上，它们是完全等价的。

• 任何可以用强归纳法证明的命题，都可以通过重新定义一个复合命题 $Q(n) = P(0) \wedge P(1) \wedge \dots \wedge P(n)$，然后对 $Q(n)$ 使用弱归纳法来证明。
• 但是，强归纳法更好用！ 就像“螺丝刀”和“电动螺丝刀”都能拧螺丝，但电动螺丝刀让你省力得多。强归纳法给了你更丰富的已知条件（归纳假设），使你在证明复杂递归和数论问题时能够游刃有余。

3.2 深度解惑：经典强归纳法定理拆解

【经典定理 1】邮票/找零问题（Theorem 3.6）

命题：对于每一个大于等于 12 的自然数 $n \ge 12$，都可以表示为 4 和 5 的线性组合。即：

$n = 4x + 5y \quad (\text{其中 } x, y \in \mathbb{N})$

为什么弱归纳法会在这里“阵亡”？

如果我们使用弱归纳法：

• IH：假设 $k = 4x + 5y$ 成立。
• 递推 $k+1$：我们需要把 $k+1$ 写成 $4$ 和 $5$ 的组合。 我们有的唯一材料是 $k = 4x + 5y$，所以 $k+1 = 4x + 5y + 1$。 问题来了：这个余出来的 $+1$ 该怎么消化？我们不能直接把 1 变成 4 或 5。除非我们分情况讨论：如果 $y \ge 1$，我们可以用一个 $4$ 替换一个 $5$（即 $+1$）；如果 $y=0$ 且 $x \ge 2$，我们得用两个 $5$ 替换三个 $4$。 虽然可以强行讨论，但证明过程变得极其繁琐、极易出错！

强归纳法的优雅解法

第一步：确定 Base Cases 因为我们每次往回退是用 $4$ 减（即通过 $P(n-4)$ 推出 $P(n)$），所以我们需要连续的 4 个 Base Cases 来启动递推链条：

• 当 $n = 12$ 时：$12 = 4 \times 3 + 5 \times 0$。成立。
• 当 $n = 13$ 时：$13 = 4 \times 2 + 5 \times 1$。成立。
• 当 $n = 14$ 时：$14 = 4 \times 1 + 5 \times 2$。成立。
• 当 $n = 15$ 时：$15 = 4 \times 0 + 5 \times 3$。成立。

第二步：归纳假设（IH） 对任意固定的 $k \ge 15$，假设对于所有满足 $12 \le i \le k$ 的整数 $i$，命题 $P(i)$ 全部成立。 (这就是强归纳的威力：我们假设 12 到 $k$ 之间所有金额的邮票都已经被我们成功凑出来了！)

第三步：归纳步骤（Inductive Step） 我们要凑出 $k+1$ 的金额。

• 因为 $k \ge 15$，所以 $k+1 \ge 16$。

• 考虑金额 $(k+1) - 4$。显然有：

  $12 \le (k+1) - 4 \le k$

• 根据强归纳假设，既然 $(k+1)-4$ 落在 $[12, k]$ 区间内，那么它一定可以被凑出来！ 即存在 $x', y' \in \mathbb{N}$，使得：

  $(k+1) - 4 = 4x' + 5y'$

• 两边同时加上 4：

  $k+1 = 4(x' + 1) + 5y'$

• 令 $x = x'+1 \in \mathbb{N}$，$y = y' \in \mathbb{N}$，我们立刻得到了 $k+1$ 的合法表示！

看！不需要任何复杂的分类讨论，我们仅仅往回退了 4 步，利用强归纳假设直接完成了证明。这就是强归纳法的降维打击。 $\quad \blacksquare$

【经典定理 2】素因子分解定理（Theorem 3.7）

命题：每一个大于 1 的自然数 $n > 1$ 都可以表示为一个或多个素数的乘积。

为什么弱归纳法无法证明？

• IH：假设 $k$ 可以写成素数的乘积。
• 递推 $k+1$：我们需要证明 $k+1$ 能写成素数的乘积。
  • 如果 $k+1$ 是素数，显然成立。
  • 如果 $k+1$ 是合数，那么它可以分解为 $k+1 = a \times b$（其中 $1 < a, b < k+1$）。 致命卡壳点：弱归纳法只允许我们假设 $P(k)$ 是真的。而 $a$ 和 $b$ 显然小于 $k$，它们极大概率不是 $k$。我们根本无法断定 $a$ 和 $b$ 是否能分解为素数乘积！证明彻底卡死。

强归纳法如何轻松破局？

• Base Case ($n=2$)：2 是素数，它本身就是“一个素数的乘积”。成立。

• 归纳假设 (IH)：对任意固定的 $k \ge 2$，假设对于所有满足 $2 \le i \le k$ 的整数 $i$，$P(i)$ 都成立（即都可以写成素数的乘积）。

• 归纳步骤 (Inductive Step)：我们来证明 $k+1$ 的情况。

  • 情况 1：$k+1$ 本身是素数。成立。

  • 情况 2：$k+1$ 是合数。这意味着它可以被拆解为两个更小的正整数的乘积：

    $k+1 = a \times b \quad (\text{其中 } 2 \le a, b \le k)$

    由于 $a$ 和 $b$ 都严格落在区间 $[2, k]$ 内，根据我们的强归纳假设，它们必然可以写成素数乘积的形式：

    $a = p_1 p_2 \dots p_r, \quad b = q_1 q_2 \dots q_s \quad (\text{其中 } p_i, q_j \text{ 均为素数})$

    那么，我们直接将它们相乘：

    $k+1 = a \times b = (p_1 p_2 \dots p_r)(q_1 q_2 \dots q_s)$

    这显然也是一个纯素数的乘积形式！

通过强归纳法，我们完美证明了素因子分解定理。 $\quad \blacksquare$

四、 递归、程序设计与归纳法的结合

归纳法不仅是纯数学工具，它更是程序设计（特别是递归算法和循环）正确性证明的基础。

4.1 斐波那契数列（Fibonacci Sequence）的最优算法分析

斐波那契数列的递归定义如下：

• $F(0) = 0, F(1) = 1$
• 对于任意 $n \ge 2$，$F(n) = F(n-1) + F(n-2)$

如果你直接把这个数学定义写成递归程序，会遇到灾难性的指数级时间复杂度。

💡 思考题证明（手写笔记第3页补充）

证明：对于所有 $n \ge 3$，斐波那契数满足 $F(n) \ge 2^{(n-1)/2}$。

证明过程（需要两个 Base Cases，因为递推式依赖前两项）：

1. Base Cases：

   • $n = 3$：左边 = $F(3) = 2$；右边 = $2^{(3-1)/2} = 2^1 = 2$。左边 $\ge$ 右边，成立。
   • $n = 4$：左边 = $F(4) = 3$；右边 = $2^{(4-1)/2} = 2^{1.5} \approx 2.83$。$3 \ge 2.83$，成立。

2. 强归纳假设 (IH)： 假设对任意固定的 $k \ge 4$，当 $3 \le i \le k$ 时，均有 $F(i) \ge 2^{(i-1)/2}$。

3. 归纳步骤 (Inductive Step)： 我们要证明 $F(k+1) \ge 2^{k/2}$。 根据定义和强归纳假设：

   $F(k+1) = F(k) + F(k-1) \ge 2^{(k-1)/2} + 2^{(k-2)/2}$

   提出公因式 $2^{(k-2)/2}$：

   $F(k+1) \ge 2^{(k-2)/2} \left(2^{1/2} + 1\right) = 2^{(k-2)/2} \left(\sqrt{2} + 1\right)$

   由于 $\sqrt{2} + 1 \approx 1.414 + 1 = 2.414 \ge 2$，因此我们有：

   $F(k+1) \ge 2^{(k-2)/2} \times 2 = 2^{(k-2)/2 + 1} = 2^{k/2}$

   这正是我们想要证明的形式！ $\quad \blacksquare$

4.2 二分查找（Binary Search）的正确性证明

二分查找是强归纳法在算法分析中应用的绝佳范例。

算法伪代码：

def findWord(W, D):
    # W: 待查单词, D: 当前词典范围（大小为 n 页）
    # Base Case
    if len(D) == 1:
        return brute_force_search(W, D[0])
    
    # Recursive Case
    mid_page = get_middle_page(D)
    W_prime = first_word_of(mid_page)
    
    if W < W_prime:
        return findWord(W, first_half_of(D))
    else:
        return findWord(W, second_half_of(D))

为什么证明二分查找的正确性必须要用强归纳法？

当我们把规模为 $k+1$ 页的词典 $D$ 减半进行递归调用时，下一轮的词典规模并不是 $k$，而是 $\lfloor (k+1)/2 \rfloor$（即大约一半的规模）。 由于规模直接发生了断崖式减小，弱归纳法的假设 $P(k)$ 在这里完全派不上用场！我们必须依靠强归纳假设——“假设对于所有页数在 $[1, k]$ 之间的词典，findWord 都能得出正确答案”。 由于 $\lfloor (k+1)/2 \rfloor \le k$，强归纳假设直接保证了缩小一半后的递归调用是正确的，从而极其自然地确立了二分查找的正确性。

五、 经典误区与 Vitamin 1a 重点辨析

5.1 所有马都是同一种颜色（Polya’s Horse Paradox）

这是一个非常有名的“假证明”（Theorem 3.8），用来警示我们在做归纳证明时必须注意微小的边界漏洞。

谬误的递推步骤： 假设对于任意 $n$ 匹马，它们的颜色都相同。 现在面对 $n+1$ 匹马 $\{h_1, h_2, \dots, h_{n+1}\}$：

• 排除最后一匹马，前 $n$ 匹马 $\{h_1, \dots, h_n\}$ 根据 IH 颜色相同（都是颜色 A）。
• 排除第一匹马，后 $n$ 匹马 $\{h_2, \dots, h_{n+1}\}$ 根据 IH 颜色也相同（都是颜色 B）。
• 因为中间的马 $\{h_2, \dots, h_n\}$ 同时属于两个集合，所以它们强行使两组马的颜色合二为一，即 颜色 A = 颜色 B。
• 结论：所有 $n+1$ 匹马颜色都相同。

❌ 漏洞在哪里？

这个递推步骤在 $n = 1 \Rightarrow n = 2$ 的跃迁中彻底失效！ 当我们有 2 匹马 $\{h_1, h_2\}$ 时：

• 前 1 匹马 $\{h_1\}$ 颜色相同。
• 后 1 匹马 $\{h_2\}$ 颜色相同。
• 但是，此时不存在任何“中间的马”来架起它们之间颜色相同的桥梁（$\{h_2, \dots, h_n\}$ 为空集）！ 因此，归纳步骤在最关键的起点就断裂了。

5.2 Vitamin 1a 核心概念深度剖析

【辨析 1】 Q1.3 的递推逻辑

• 问题：已知 $(P(k) \wedge (\forall n \in \mathbb{N})(P(n) \Rightarrow P(n+1)))$，是否能推出对所有自然数，有 $(\forall n \in \mathbb{N})(n < k \vee P(n))$ 成立？
• 解答：True。
  • 这里的逻辑表达式 $(n < k \vee P(n))$ 意思是： 对于任意自然数 $n$，要么 $n$ 小于起始界限 $k$，要么 $P(n)$ 为真。
  • 换句话说，它断言：只要 $n \ge k$，那么 $P(n)$ 必定为真。
  • 既然基准情况从 $P(k)$ 开始成立，且有递推关系 $P(n) \Rightarrow P(n+1)$，那么多米诺骨牌就会从第 $k$ 块开始向后全部倒下。因此，所有 $\ge k$ 的项全部成立。

【辨析 2】 什么样的地图才是“两着色”的？（Q2.2）

• 问题：是否所有的地图（不一定由直线划分）都是两可着色（Two-colorable）的？
• 解答：False。
  • 两着色定理（Theorem 3.3）*仅适用于*由穿过整个区域的连续直线（或大圆）分割而成的地图。
  • 如果允许任意曲线或不穿过边界的割线，很容易构造出互邻的三块区域（例如一个圆形区域被三等分，或者三个同心圆相切），它们是无法用两种颜色涂满且邻接处不重色的。

(注：左侧直线划分的地图必定是二部图形式，可以用两色渲染；右侧包含三岔路口或环套环的普通地图，则需要至少三色或四色。)