11 年级

数学归纳法

通过奠基步与归纳步证明关于全体自然数的命题，强归纳法、良序原理，以及归纳法失效的情形。

想象一排无限延伸、竖直站立的多米诺骨牌。怎样才能确信每一张骨牌都会倒下？只需满足两个条件：(1) 推倒第一张骨牌；(2) 只要任意一张骨牌倒下，它都离得足够近，能把下一张骨牌撞倒。数学归纳法正是把这种多米诺连锁反应转化为严格证明方法的工具，用来证明关于全体自然数 $n = 1, 2, 3, \dots$ 的命题。

中学数学归纳法原理

定理: 数学归纳法原理

设 $P(n)$ 是关于正整数 $n$ 的命题。如果 (1) 奠基步： $P(1)$ 成立；且 (2) 归纳步：对任意整数 $k \ge 1$ ，假设 $P(k)$ 成立（归纳假设）能推出 $P(k+1)$ 也成立，那么 $P(n)$ 对所有整数 $n \ge 1$ 都成立。

为什么成立?

由 $P(1)$ 和蕴含式 $P(1) \Rightarrow P(2)$ 可得 $P(2)$ ；由 $P(2)$ 和 $P(2) \Rightarrow P(3)$ 可得 $P(3)$ ；如此继续，经过有限步就能到达任意给定的整数 $n$ 。在公理化算术（皮亚诺公理）中，归纳原理是定义自然数的核心公理之一。

证明

假设 $P(1)$ 成立，且对任意整数 $k \ge 1$ 蕴含式 $P(k) \Rightarrow P(k+1)$ 成立。为证明 $P(n)$ 对所有 $n \ge 1$ 成立，用反证法假设反例集合 $S = \{n \in \mathbb{Z}_{\ge 1} : P(n) \text{ is false}\}$ 非空。

根据正整数集 $\mathbb{Z}_{\ge 1}$ 的良序原理，非空子集 $S$ 必有最小元 $m = \min S \ge 1$ 。由于奠基步假设 $P(1)$ 为真，故 $1 \notin S$ ，从而必有 $m \ge 2$ ，即 $m - 1 \ge 1$ 。

因为 $m - 1 < m$ 且 $m$ 是 $S$ 的最小元，所以 $m - 1 \notin S$ ，即 $P(m-1)$ 为真。对 $k = m - 1 \ge 1$ 应用归纳步可得 $P(m-1) \Rightarrow P(m)$ ，故 $P(m)$ 为真。这与 $m \in S$ 矛盾，从而 $S = \varnothing$ ，即 $P(n)$ 对所有 $n \ge 1$ 都成立。

\bigl(P(1) \;\wedge\; \forall k \ge 1,\; (P(k) \Rightarrow P(k+1))\bigr) \;\Longrightarrow\; \forall n \ge 1,\; P(n)

例题: 前 n 个正整数之和

证明：对任意整数 $n \ge 1$ ， $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ 。

解答

**奠基步 ( $n = 1$ )：** 左边为 $1$ ，右边为 $\frac{1(1+1)}{2} = 1$ ，故 $P(1)$ 成立。

归纳步： 假设 $P(k)$ 对某个 $k \ge 1$ 成立，即 $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$ 。将 $k + 1$ 加到两边，得 $1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}$ ，这正是 $P(k+1)$ 。由数学归纳法，该公式对所有 $n \ge 1$ 成立。

\sum_{j=1}^{n} j^2 = 1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n

离散求和与连续面积的可视化：调节矩形个数

n

，将阶梯和

\sum_{j=1}^{n} j^2 = \frac{n(n+1)(2n+1)}{6}

与积分

\int_0^n x^2\,dx = \frac{n^3}{3}

进行对比，直观展示每一步归纳如何添上下一列面积为

(k+1)^2

的矩形条。

例题: 一个指数不等式

证明 $2^n > n$ 对任意整数 $n \ge 1$ 成立。

解答

**奠基步 ( $n = 1$ )：** $2^1 = 2 > 1$ ，成立。

归纳步： 假设 $2^k > k$ 对某个 $k \ge 1$ 成立。两边同乘 $2$ 得 $2^{k+1} = 2 \cdot 2^k > 2k = k + k \ge k + 1$ （因为 $k \ge 1$ ）。因此 $2^{k+1} > k + 1$ ，归纳完成。

大学强归纳法与良序原理

定义: 强归纳法（完全归纳法）

要证明 $P(n)$ 对所有 $n \ge n_0$ 成立，只需验证 $P(n_0)$ ，并证明对任意 $k \ge n_0$ ，若 $P(n_0), P(n_0+1), \dots, P(k)$ 全都成立，则 $P(k+1)$ 成立。尽管名为强归纳法，它在逻辑上与普通归纳法等价：只需对合取命题 $Q(n) = P(n_0) \wedge P(n_0+1) \wedge \cdots \wedge P(n)$ 应用普通归纳法即可。

定理: 强归纳法原理及其逻辑等价性

设 $P(n)$ 是关于整数 $n \ge n_0$ 的命题。若 $P(n_0)$ 成立，且对任意整数 $k \ge n_0$ 蕴含式 $\bigl(P(n_0) \wedge \cdots \wedge P(k)\bigr) \Rightarrow P(k+1)$ 成立，则 $P(n)$ 对所有整数 $n \ge n_0$ 都成立。此外，强归纳法、普通归纳法与良序原理在逻辑上彼此等价。

为什么成立?

强归纳法允许我们回溯使用任意较早的情形 $P(j)$ （其中 $n_0 \le j \le k$ ，例如分解 $k+1 = a b$ 时的因子 $a, b \le k$ ，或斐波那契递推中的 $P(k-1)$ 与 $P(k)$ ），而无需在普通归纳法之外引入任何新公理。

证明

归结为普通归纳法： 给定关于 $n \ge n_0$ 的谓词 $P(n)$ ，定义累积合取命题 $Q(n) \equiv P(n_0) \wedge P(n_0+1) \wedge \cdots \wedge P(n)$ 。在起始指标 $n = n_0$ 处， $Q(n_0)$ 仅含单项 $P(n_0)$ ，由强归纳法的奠基假设知其成立。

**关于 $Q(k)$ 的归纳步：** 固定整数 $k \ge n_0$ 并假设 $Q(k)$ 为真。由 $Q(k)$ 的定义知 $P(n_0), P(n_0+1), \dots, P(k)$ 全部为真。于是由强归纳步假设 $\bigl(P(n_0) \wedge \cdots \wedge P(k)\bigr) \Rightarrow P(k+1)$ 推出 $P(k+1)$ 也为真。

结论： 将 $Q(k)$ 与 $P(k+1)$ 结合即得 $Q(k+1) \equiv Q(k) \wedge P(k+1)$ 。对命题 $Q(n)$ 应用普通数学归纳法可知，对所有整数 $n \ge n_0$ 均有 $Q(n)$ 成立；特别地，其最后一个合取项 $P(n)$ 对所有 $n \ge n_0$ 都成立。

例题: 素因数分解的存在性

证明：每个整数 $n \ge 2$ 要么是素数，要么是若干个素数的乘积。

解答

**奠基步 ( $n = 2$ )：** $2$ 是素数。

强归纳步： 固定 $k \ge 2$ ，假设每个整数 $m$ （满足 $2 \le m \le k$ ）都是素数或素数的乘积。考察 $k + 1$ 。若 $k + 1$ 是素数则证毕；否则 $k + 1 = a b$ ，其中整数 $a, b$ 满足 $2 \le a, b \le k$ 。普通归纳法在此无法奏效，因为 $a$ 和 $b$ 并不等于 $k$ ，只满足 $\le k$ 。由强归纳假设， $a$ 和 $b$ 都是素数的乘积，因此它们的乘积 $k + 1 = a b$ 也是素数的乘积。

定义: 良序原理

正整数集的每个非空子集 $S \subseteq \mathbb{N}$ 都有一个最小元 $m \in S$ ，使得 $m \le x$ 对所有 $x \in S$ 成立。

良序原理、普通归纳法与强归纳法是同一原理的三种面貌。要由良序原理推出归纳法，假设 $P(1)$ 成立且 $P(k) \Rightarrow P(k+1)$ 对所有 $k \ge 1$ 成立，但 $P(n)$ 对某个 $n$ 不成立。此时反例集合 $S = \{n \ge 1 : P(n) \text{ is false}\}$ 非空，由良序原理它有最小元 $m$ 。不可能有 $m = 1$ ，因为 $P(1)$ 为真；故 $m - 1 \ge 1$ 不在 $S$ 中，即 $P(m-1)$ 为真。由归纳步可知 $P(m)$ 也必为真，这与 $m \in S$ 矛盾。这种表述常称为最小反例法。

进阶几何归纳法：用三格骨牌铺棋盘

例题: 戈隆布三格骨牌铺砖问题（1954年）

L形三格骨牌是由 $3$ 个单位正方形排成L形的骨牌。证明：对任意整数 $n \ge 1$ ，将 $2^n \times 2^n$ 棋盘去掉任意一格后，总可以用互不重叠的L形三格骨牌完全铺满。

解答

注意，将命题加强为去掉任意一格（而非仅限角上一格）正是归纳法得以推进的关键。**奠基步 ( $n = 1$ )：** 从 $2 \times 2$ 棋盘去掉任意一格后剩下由 $3$ 格组成的L形，恰好可用 $1$ 块三格骨牌覆盖。

归纳步： 假设命题对 $2^k \times 2^k$ 棋盘成立。将缺一格的 $2^{k+1} \times 2^{k+1}$ 棋盘分成四个 $2^k \times 2^k$ 象限。缺失的那一格位于其中一个象限。在棋盘中心放置一块L形三格骨牌，使其 $3$ 个方格分别盖住其余三个象限靠近中心的一格。此时每个 $2^k \times 2^k$ 象限都恰好缺少一格，由归纳假设知四个象限均可完全铺满。

研究微妙的陷阱与归纳法的局限

常见错误. 波利亚谬误：“所有马都是同一种颜色”。 设

P(n)

为：在任意

n

匹马的集合中，所有马颜色相同。**奠基步 (

n = 1

)： 一匹马显然与自身同色。“归纳步”：** 给定

k + 1

匹马

\{h_1, h_2, \dots, h_{k+1}\}

，前

k

匹马

\{h_1, \dots, h_k\}

由

P(k)

知同色，后

k

匹马

\{h_2, \dots, h_{k+1}\}

也由

P(k)

知同色；由于中间的马

\{h_2, \dots, h_k\}

同时属于两组，故全部

k + 1

匹马必定同色！错在哪里？ 蕴含式

P(k) \Rightarrow P(k+1)

恰在

k = 1

处失效：当

k + 1 = 2

匹马时，两个子集

\{h_1\}

与

\{h_2\}

的交集为空

\{h_2, \dots, h_k\} = \varnothing

，没有任何公共的马能把两组的颜色连接起来。

为什么并非所有关于整数的真命题都能直接通过对 $n$ 的归纳法证明？一个典型例子是考拉兹猜想（`collatz-conjecture`，1937年提出）：从任意正整数 $n$ 出发，反复将偶数 $x$ 变为 $x/2$ 、将奇数 $x$ 变为 $3x + 1$ ，猜想断言该轨道总会到达 $1$ 。若尝试对 $n$ 使用强归纳法，偶数 $2k$ 会立即降为 $k < 2k$ ，可以归结为归纳假设；但奇数 $2k + 1$ 却会向上跳到 $6k + 4 > 2k + 1$ ，超出了归纳假设 $P(1), \dots, P(2k+1)$ 所覆盖的范围。

用数学归纳法证明命题 $P(n)$ 对所有 $n \ge 1$ 成立时，归纳步必须证明什么？

波利亚关于“所有马都是同一种颜色”的伪归纳证明在哪里失效？

强归纳法与普通归纳法有何不同？

为什么对 $n$ 直接使用强归纳法无法证明考拉兹猜想？

参考文献

Florian Cajori (1918). Origin of the Name 'Mathematical Induction' · DOI:10.1080/00029890.1918.11998404
Solomon W. Golomb (1954). Checkerboards and Polyominoes · DOI:10.1080/00029890.1954.11988548
David Bařina (2021). Convergence verification of the Collatz problem · DOI:10.1007/s11227-020-03368-x