3.4 数学归纳法与强归纳法

前几节通过任取对象来证明全称命题。有些命题按照连续整数编号：

P(1),P(2),P(3),\ldots

而且一个情形能够自然支撑后续情形。数学归纳法（mathematical induction）把这种依赖关系变成证明方法。

归纳法不是检查许多例子。它证明一个起点和一条一般传递规则，两者结合后覆盖无限多个情形。

数学归纳法的两个组成部分

要证明每个整数 $n\ge n_0$ 都满足 $P(n)$ ，普通归纳法需要：

1. 基础情形（base case）：证明 $P(n_0)$ ；

2. 归纳步骤（inductive step）：任取 $k\ge n_0$ ，假设 $P(k)$ ，再证明 $P(k+1)$ 。

临时假设 $P(k)$ 叫作归纳假设（inductive hypothesis）。我们没有假设完整定理，而是暂时取得任意一个情形，以证明真值能够传到下一个情形。

逻辑结构是

P(n_0) \quad\text{且}\quad \forall k\ge n_0,\;P(k)\to P(k+1).

为什么它能够覆盖全部情形？

基础情形建立 $P(n_0)$ ；

归纳步骤给出 $P(n_0+1)$ ；

再应用一次归纳步骤，得到 $P(n_0+2)$ ；

连锁会经过所有不小于 $n_0$ 的整数。

多米诺比喻只有在记住两个部分时才有用。没有推倒第一块，直立多米诺不会自动倒下；如果间距规则存在断点，推倒一块也无法影响其余部分。

正在加载交互实验...

请改变归纳步跨度。规则 $P(k)\to P(k+2)$ 不会连接奇数编号与偶数编号。一个基础情形只能启动其中一条链；增加第二个基础情形才能覆盖另一条。模拟会准确显示当前基础与步骤究竟证明了哪些命题。

正在加载概念检查...

正在加载本节练习...

一个完整的求和公式归纳证明

我们要证明：对每个正整数 $n$ ，

1+2+\cdots+n=\frac{n(n+1)}{2}.

省略号表示从 $1$ 到 $n$ 的所有连续整数都要相加。

定义命题

P(n):\quad 1+2+\cdots+n=\frac{n(n+1)}{2}.

基础情形

当 $n=1$ 时，左侧为 $1$ ，右侧为

\frac{1(1+1)}{2}=1.

所以 $P(1)$ 为真。

归纳假设

任取 $k\ge1$ ，假设 $P(k)$ 成立：

1+2+\cdots+k=\frac{k(k+1)}{2}.

这个假设是证明下一情形的工具。必须明确写出它，才能看清后面究竟允许替换哪一部分。

归纳步骤

第 $k+1$ 个情形多出一个新项：

1+2+\cdots+k+(k+1).

使用归纳假设替换前面的和：

\begin{aligned} 1+2+\cdots+k+(k+1) &=\frac{k(k+1)}{2}+(k+1)\\ &=\frac{k(k+1)+2(k+1)}{2}\\ &=\frac{(k+1)(k+2)}{2}. \end{aligned}

最终式恰好是把公式中的 $n$ 换成 $k+1$ ：

\frac{(k+1)((k+1)+1)}{2}.

因此， $P(k)$ 可以推出 $P(k+1)$ 。

结论

基础情形 $P(1)$ 成立，并且对每个 $k\ge1$ ， $P(k)\to P(k+1)$ 都成立。根据数学归纳法，

1+2+\cdots+n=\frac{n(n+1)}{2}

对每个正整数 $n$ 成立。

归纳证明中的常见断点

错误	为什么失败
只检查 $n=1,2,3$	有限例子不能覆盖全部 $n$
证明归纳步骤却省略基础情形	蕴含链没有经过验证的起点
为证明 $P(k+1)$ 而直接假设 $P(k+1)$	这是预先假设目标，而不是推导目标
最终表达式没有匹配 $P(k+1)$	归纳步骤尚未到达目标
步长为 $2$ 却只有一个基础情形	可能只覆盖一个奇偶编号链

结束前，应指出归纳假设究竟在哪一行被使用。如果从未使用，它可能是一个有效的直接证明，也可能缺少了归纳法的关键连接。

强归纳法可以使用全部更早情形

强归纳法（strong induction）的归纳假设会取得从起点到 $k$ 的全部情形：

P(n_0),P(n_0+1),\ldots,P(k),

再使用它们证明 $P(k+1)$ 。

普通归纳法只假设 $P(k)$ ；强归纳法能够使用整段已经验证的历史。两种方法的证明能力相同，但其中一种可能更符合题目的依赖结构。

当下一个对象由某个更小对象构造，而这个对象不一定是紧邻前一项时，强归纳法尤其自然。后续课程中的递归算法、因数分解和树结构都会出现这种依赖。

邮资问题的强归纳证明

定理。 每个不小于 $12$ 的整数邮资 $n$ ，都能只使用面值 $4$ 与 $5$ 的邮票组成。

先验证四个连续基础情形：

\begin{aligned} 12&=4+4+4,\\ 13&=4+4+5,\\ 14&=4+5+5,\\ 15&=5+5+5. \end{aligned}

现在任取 $k\ge16$ ，假设从 $12$ 到 $k-1$ 的每个金额都能组成。我们要组成 $k$ 。

因为

k-4\ge12,

所以 $k-4$ 属于强归纳假设覆盖的更早情形。先用面值 $4$ 、 $5$ 的邮票组成 $k-4$ ，再增加一张面值 $4$ 的邮票，得到

(k-4)+4=k.

因此， $k$ 也能组成。根据强归纳法，每个 $n\ge12$ 都能组成。

为什么需要四个基础情形？归纳步骤每次向前增加 $4$ ，连续的 $12,13,14,15$ 分别启动四条余数链。只有一个基础情形会留下断点。

正在加载交互实验...

请改变邮票面值和声称成立的起始金额。地图会区分真正可达与“较大数应该都可以”的愿望。使用 $4$ 、 $5$ 时，先检查连续基础窗口，再把每个后续金额追踪到某个更早可达金额。

正在加载概念检查...

正在加载本节练习...

注意

强归纳法并不是未经证明就假设完整定理。更早情形之所以可用，是因为基础情形和此前的归纳步骤已经建立了它们。

章节衔接

第 3 章建立了一套证明工具：精确定义、反例、直接证明、分情况、逆否、反证、见证、唯一性与归纳法。第 4 章会用这些方法研究函数和关系。定义会变得更丰富，但证明问题仍然熟悉：必须证明什么？哪种证据足够？哪条策略能让逻辑依赖最清楚？

3.4 数学归纳法与强归纳法

前几节通过任取对象来证明全称命题。有些命题按照连续整数编号：

P(1),P(2),P(3),\ldots

而且一个情形能够自然支撑后续情形。数学归纳法（mathematical induction）把这种依赖关系变成证明方法。

归纳法不是检查许多例子。它证明一个起点和一条一般传递规则，两者结合后覆盖无限多个情形。

数学归纳法的两个组成部分

要证明每个整数 $n\ge n_0$ 都满足 $P(n)$ ，普通归纳法需要：

1. 基础情形（base case）：证明 $P(n_0)$ ；

2. 归纳步骤（inductive step）：任取 $k\ge n_0$ ，假设 $P(k)$ ，再证明 $P(k+1)$ 。

临时假设 $P(k)$ 叫作归纳假设（inductive hypothesis）。我们没有假设完整定理，而是暂时取得任意一个情形，以证明真值能够传到下一个情形。

逻辑结构是

P(n_0) \quad\text{且}\quad \forall k\ge n_0,\;P(k)\to P(k+1).

为什么它能够覆盖全部情形？

基础情形建立 $P(n_0)$ ；

归纳步骤给出 $P(n_0+1)$ ；

再应用一次归纳步骤，得到 $P(n_0+2)$ ；

连锁会经过所有不小于 $n_0$ 的整数。

多米诺比喻只有在记住两个部分时才有用。没有推倒第一块，直立多米诺不会自动倒下；如果间距规则存在断点，推倒一块也无法影响其余部分。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

一个完整的求和公式归纳证明

我们要证明：对每个正整数 $n$ ，

1+2+\cdots+n=\frac{n(n+1)}{2}.

省略号表示从 $1$ 到 $n$ 的所有连续整数都要相加。

定义命题

P(n):\quad 1+2+\cdots+n=\frac{n(n+1)}{2}.

基础情形

当 $n=1$ 时，左侧为 $1$ ，右侧为

\frac{1(1+1)}{2}=1.

所以 $P(1)$ 为真。

归纳假设

任取 $k\ge1$ ，假设 $P(k)$ 成立：

1+2+\cdots+k=\frac{k(k+1)}{2}.

这个假设是证明下一情形的工具。必须明确写出它，才能看清后面究竟允许替换哪一部分。

归纳步骤

第 $k+1$ 个情形多出一个新项：

1+2+\cdots+k+(k+1).

使用归纳假设替换前面的和：

\begin{aligned} 1+2+\cdots+k+(k+1) &=\frac{k(k+1)}{2}+(k+1)\\ &=\frac{k(k+1)+2(k+1)}{2}\\ &=\frac{(k+1)(k+2)}{2}. \end{aligned}

最终式恰好是把公式中的 $n$ 换成 $k+1$ ：

\frac{(k+1)((k+1)+1)}{2}.

因此， $P(k)$ 可以推出 $P(k+1)$ 。

结论

基础情形 $P(1)$ 成立，并且对每个 $k\ge1$ ， $P(k)\to P(k+1)$ 都成立。根据数学归纳法，

1+2+\cdots+n=\frac{n(n+1)}{2}

对每个正整数 $n$ 成立。

归纳证明中的常见断点

错误	为什么失败
只检查 $n=1,2,3$	有限例子不能覆盖全部 $n$
证明归纳步骤却省略基础情形	蕴含链没有经过验证的起点
为证明 $P(k+1)$ 而直接假设 $P(k+1)$	这是预先假设目标，而不是推导目标
最终表达式没有匹配 $P(k+1)$	归纳步骤尚未到达目标
步长为 $2$ 却只有一个基础情形	可能只覆盖一个奇偶编号链

结束前，应指出归纳假设究竟在哪一行被使用。如果从未使用，它可能是一个有效的直接证明，也可能缺少了归纳法的关键连接。

强归纳法可以使用全部更早情形

强归纳法（strong induction）的归纳假设会取得从起点到 $k$ 的全部情形：

P(n_0),P(n_0+1),\ldots,P(k),

再使用它们证明 $P(k+1)$ 。

普通归纳法只假设 $P(k)$ ；强归纳法能够使用整段已经验证的历史。两种方法的证明能力相同，但其中一种可能更符合题目的依赖结构。

邮资问题的强归纳证明

定理。 每个不小于 $12$ 的整数邮资 $n$ ，都能只使用面值 $4$ 与 $5$ 的邮票组成。

先验证四个连续基础情形：

\begin{aligned} 12&=4+4+4,\\ 13&=4+4+5,\\ 14&=4+5+5,\\ 15&=5+5+5. \end{aligned}

现在任取 $k\ge16$ ，假设从 $12$ 到 $k-1$ 的每个金额都能组成。我们要组成 $k$ 。

因为

k-4\ge12,

所以 $k-4$ 属于强归纳假设覆盖的更早情形。先用面值 $4$ 、 $5$ 的邮票组成 $k-4$ ，再增加一张面值 $4$ 的邮票，得到

(k-4)+4=k.

因此， $k$ 也能组成。根据强归纳法，每个 $n\ge12$ 都能组成。

为什么需要四个基础情形？归纳步骤每次向前增加 $4$ ，连续的 $12,13,14,15$ 分别启动四条余数链。只有一个基础情形会留下断点。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

注意

强归纳法并不是未经证明就假设完整定理。更早情形之所以可用，是因为基础情形和此前的归纳步骤已经建立了它们。