4.4 数学归纳法（选学）

第 1 步

从例子进入

桌上立着一长排多米诺骨牌，一共 $100$ 块。摆的时候已经检查过：每一块倒下时，都一定会碰倒紧挨着它的下一块。现在把第 $1$ 块推倒。点下面的按钮，试试三种情况：

互动演示载入中

想一想

第 $100$ 块会倒吗？

看答案与解析

答案：A

A。第 $1$ 块倒了，碰倒第 $2$ 块；第 $2$ 块倒了，碰倒第 $3$ 块……一直传到第 $100$ 块。不用一块一块看，因为两件事已经够了：

第一块倒了（有人推）；
任何一块倒了，下一块一定倒（摆得够近）。

少了哪一件都不行：没人推，一块也不倒；中间有两块离得太远，后面的就都立着。这一节就把这个想法变成证明方法：数学归纳法。

第 2 步

讲清楚

1. 先认识几个词

要用到：数列的通项和递推公式（回看 4.1）、等差数列求和（回看 4.2）、等比数列求和（回看 4.3）。

互动演示载入中

双柱基石

奠基步 vs 传递步（缺一不可）

仅有传递无奠基：纯理论推演但无现实基底，如「 $n^{2} + n + 1$ 是偶数」传递成立但全盘为伪。
仅有奠基无传递：验算前 100 项成立也不代表无限（欧拉质数多项式 $n = 40$ 破灭）。
双柱合璧：奠基确定起点真值，传递延续真值无穷延展。

假设规范

归纳假设的合法使用

合法使用：对任意 $k \geq n_{0}$ ，把 $P (k)$ 作为已知前提，交代如何推出 $P (k + 1)$ ，不能直接假定下一项成立。若下一项能独立证明，推理仍可能有效，应说明采用了直接证明。
非法禁忌：绝不可直接假设「对所有 $n$ 都成立」；亦不可在证明中对假设弃之不用。
核心枢纽：归纳步的本质是证明条件命题「 $P (k) ⟹ P (k + 1)$ 」。

2. 两步证明法则与色彩语义主公式

要证明对所有整数 $n \geq n_{0}$ ，命题 $P (n)$ 恒成立，需严格完成以下两步：

想一想

自己试试：用归纳法证明 $1 + 2 + 3 + \dots + n = \frac{n ( n + 1 )}{2}$ 。从 $n = k$ 到 $n = k + 1$ ，左边多了哪一项？

看答案与解析

答案：B

B。 $n = k$ 时末项是 $k$ ， $n = k + 1$ 时末项是 $k + 1$ ，多出的正是第 $k + 1$ 项。选 D 是死套了例 1（例 1 通项是 $2 n - 1$ ）。

3. 归纳步书写与三步破题思维链

典型例题：数列通项猜想的完整归纳证明

信号

题目给出一个关于所有自然数 $n \geq n_{0}$ 的恒等式或通项猜想，要求严格证明。

步骤

奠基

假设

传递

注明使用归纳假设

防坑

要交代从归纳假设到下一项的论证，不能跳过推导直接写结论；独立的直接证明并不因此无效。题目指定归纳法时，还须按要求展示该方法，结尾写明成立范围。

想一想

自己试试： $a_{1} = 1$ ， $a_{n + 1} = \frac{a _{n}}{1 + a _{n}}$ 。先算前三项： $1, \frac{1}{2}, \frac{1}{3}$ ，猜想 $a_{n} = \frac{1}{n}$ 。在归纳步中，将 $a_{k} = \frac{1}{k}$ 直接代入递推式，尚未化简时得到哪个式子？

看答案与解析

答案：A

A。把 $a_{k} = \frac{1}{k}$ 代入 $a_{k + 1} = \frac{a _{k}}{1 + a _{k}}$ ，尚未化简的式子是 $\frac{\frac{1}{k}}{1 + \frac{1}{k}}$ 。C 的 $\frac{1}{k + 1}$ 与 A 数学上相等，但它已经化简；本题特意问直接代入、尚未化简的形式。

4. 起点不一定是 1

命题若从 $n_{0}$ 开始，奠基就验证 $P (n_{0})$ ，传递则在 $k \geq n_{0}$ 的前提下证明。

想一想

自己试试：不等式 $n! > 2^{n}$ 从哪个正整数起开始成立，且之后一直成立？

看答案与解析

答案：C

C。 $1! = 1 < 2, 2! = 2 < 4, 3! = 6 < 8, 4! = 24 > 16$ 。当 $k \geq 4$ 时传递步成立： $(k + 1)! = (k + 1) k! > (k + 1) 2^{k} > 2 \cdot 2^{k} = 2^{k + 1}$ 。选 B 是把 $3!$ 与 $2^{3}$ 算反了。

5. 三大翻车现场红绿对比卡

互动演示载入中

再深一点（可以先跳过）

为什么两步就足够：反证法。若有反例，必存在最小的反例 $m$ 。因 $m \neq = n_{0}$ ，则前一项 $m - 1$ 必定成立；但传递性保证 $P (m - 1) ⟹ P (m)$ 成立，矛盾。

强归纳法：有时递推依赖前面多项（如斐波那契数列），可假设对所有 $n \leq k$ 均成立，再证 $k + 1$ 。

覆盖范围：验证起始情形，再证明每一步都能传递，才能覆盖从起点开始的全部待证整数；结论不能越过起点向前扩展。

第 3 步

动手

① 多米诺：奠基和传递少一个会怎样

勾掉「推倒起点那一块」看看；点两块之间的小圆（或选中后按回车、空格）把间距拉开，红色表示「太远，碰不到下一块」。左右方向键在小圆之间移动。也可以改起点 $n_{0}$ 。

互动演示载入中

② 进阶：拖 n，看从 k 到 k+1 多了什么

选一个命题，拖滑块（或按方向键）改 $n$ ，也可以在下面那排圆点上点或拖。圆点绿色是这个 $n$ 成立，红色是不成立。看看哪个命题能用归纳法证，哪个不能。

互动演示载入中

第 4 步

练一练

从易到难排好了。前两道直接用，中间三道是最常见的错，最后一道是挑战。

直接用

想一想

用归纳法证明 $1 + 2 + 2^{2} + \dots + 2^{n - 1} = 2^{n} - 1$ 。从 $n = k$ 到 $n = k + 1$ ，左边要加上哪一项？

看答案与解析

答案：A

A。第 $n$ 项是 $2^{n - 1}$ ， $n = k + 1$ 时最后一项是 $2^{(k + 1) - 1} = 2^{k}$ 。加上后： $(2^{k} - 1) + 2^{k} = 2^{k + 1} - 1$ ，正是 $n = k + 1$ 时的右边。选 B 是把「第 $k + 1$ 项」当成了 $2^{k + 1}$ ，忘了指数是 $n - 1$ 。

想一想

用归纳法证明 $1^{2} + 2^{2} + \dots + n^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}$ 。归纳步要证的目标式是？

看答案与解析

答案：A

A。把右边的 $n$ 全换成 $k + 1$ ： $n + 1 \to k + 2$ ， $2 n + 1 \to 2 (k + 1) + 1 = 2 k + 3$ 。B 是 $P (k)$ 的右边（那是归纳假设，不是目标）；C 把 $2 n + 1$ 换成了 $2 k + 2$ ，少加了 $1$ 。

易错

想一想

小明「证明」 $n^{2} + n + 1$ 是偶数：「假设 $k^{2} + k + 1$ 是偶数，则 $(k + 1)^{2} + (k + 1) + 1 = (k^{2} + k + 1) + 2 (k + 1)$ 也是偶数，所以对所有正整数 $n$ 成立。」这个证明——

看答案与解析

答案：B

B。传递确实没算错（所以 C 不对），可只有传递不够：没有验证 $P (1)$ 。一验就露馅： $1 + 1 + 1 = 3$ 是奇数。实际上 $n (n + 1)$ 是偶数， $n^{2} + n + 1$ 永远是奇数。两步缺一不可，这里缺的是奠基。

想一想

有人算出 $n^{2} + n + 41$ 在 $n = 1, 2, \dots, 39$ 时都是质数，于是写：「由此类推，对所有正整数 $n$ ， $n^{2} + n + 41$ 都是质数。」

看答案与解析

答案：C

C。 $n = 40$ 时 $4 0^{2} + 40 + 41 = 1681 = 41 \times 41$ ，不是质数。只验证有限项、写「由此类推」都不是证明，相当于只看了前 39 块骨牌，没有「任意一块倒、下一块就倒」这一步。在「动手」②里选第三个命题，拖到 $40$ 看看。

想一想

一份证明 $1 + 3 + \dots + (2 n - 1) = n^{2}$ 的作业：「(1) $n = 1$ 时 $1 = 1^{2}$ ，成立。(2) 假设 $n = k$ 时成立。 $n = k + 1$ 时， $1 + 3 + \dots + (2 k + 1) = (k + 1)^{2}$ ，所以也成立。」问题出在哪？

看答案与解析

答案：B

B。(2) 里「 $= (k + 1)^{2}$ 」正是要证的结论，这里直接写上去，等于先假设了最终结论。要像例 1 那样：把左边拆成 $[1 + 3 + \dots + (2 k - 1)] + (2 k + 1)$ ，用归纳假设换成 $k^{2} + (2 k + 1)$ ，再算出 $(k + 1)^{2}$ 。C 不对：命题从 $n = 1$ 说起，奠基就验证 $n = 1$ 。

挑战

想一想

$\frac{1}{1 \times 2} + \frac{1}{2 \times 3} + \dots + \frac{1}{99 \times 100} =$ ？

看答案与解析

答案：A

A。每一项都能拆开： $\frac{1}{k ( k + 1 )} = \frac{1}{k} - \frac{1}{k + 1}$ 。加起来中间全部抵消： $(1 - \frac{1}{2}) + (\frac{1}{2} - \frac{1}{3}) + \dots + (\frac{1}{99} - \frac{1}{100}) = 1 - \frac{1}{100} = \frac{99}{100}$ 。

同样的拆法对任意 $n$ 直接证明了 $\frac{1}{1 \times 2} + \dots + \frac{1}{n ( n + 1 )} = \frac{n}{n + 1}$ ，不用归纳法。（用归纳法也能证，归纳步要算 $\frac{k}{k + 1} + \frac{1}{( k + 1 ) ( k + 2 )} = \frac{k + 1}{k + 2}$ 。）能直接变形的，不必硬用归纳。

第 5 步

高考真题

先独立作答，做完再对照分步解析。选择题点选项自动判对错；填空题写法不同时，看答案自己判。要用到后面章节的题收在最后，学到那里再做。

2012 湖北卷（理科）第 22 题 · 解答

本题第(II)问中的二元命题为：设 $a_{1} \geq 0, a_{2} \geq 0$ ， $b_{1}, b_{2}$ 为正有理数，若 $b_{1} + b_{2} = 1$ ，则 $a_{1}^{b_{1}} a_{2}^{b_{2}} \leq a_{1} b_{1} + a_{2} b_{2}$ 。 (III) 请将(II)中的命题推广到一般形式，并用数学归纳法证明你所推广的命题。

答案与解析

答案：对每个整数 $n \geq 2$ ，若 $a_{1}, \dots, a_{n} \geq 0$ ， $b_{1}, \dots, b_{n}$ 为正有理数且和为1，则 $i = 1 \prod n a_{i}^{b_{i}} \leq i = 1 \sum n b_{i} a_{i} .$

思路

先把前 $k$ 个权重归一化为和为1，再把这 $k$ 项整体与最后一项组成二元问题。

明确命题与基步
设 $P (n)$ 为：对任意非负 $a_{1}, \dots, a_{n}$ 及和为1的正有理权重 $b_{1}, \dots, b_{n}$ ，乘积 $\prod_{i = 1}^{n} a_{i}^{b_{i}}$ 不大于加权和 $\sum_{i = 1}^{n} b_{i} a_{i}$ 。 $n = 2$ 正是原题第(II)问已建立的二元命题，所以基步成立。本小问引用该前问结论，不需重做前问的导数计算。
写出归纳假设
假设对某个 $k \geq 2$ ， $P (k)$ 成立，即所有满足条件的 $k$ 元数据都满足相应不等式。现考虑 $k + 1$ 元数据；若某个 $a_{i} = 0$ ，乘积为0而加权和非负，结论立即成立。因此以下只需处理各 $a_{i} > 0$ 。
对前 $k$ 项归一化并使用假设
记 $B = b_{1} + \dots + b_{k} = 1 - b_{k + 1},$ 故 $0 < B < 1$ 。令 $c_{i} = \frac{b _{i}}{B}$ ，则 $c_{i}$ 均为正有理数且 $\sum_{i = 1}^{k} c_{i} = 1$ 。由归纳假设，令 $G C = i = 1 \prod k a_{i}^{c_{i}}, = i = 1 \sum k c_{i} a_{i},$ 有 $G \leq C$ 。
由二元命题推出下一阶
因为 $B > 0$ ， $G^{B} \leq C^{B}$ 。对 $C$ 与 $a_{k + 1}$ 使用第(II)问二元命题，权重为 $B$ 与 $b_{k + 1}$ ，得到 $i = 1 \prod k + 1 a_{i}^{b_{i}} = G^{B} a_{k + 1}^{b_{k + 1}} \leq C^{B} a_{k + 1}^{b_{k + 1}} \leq B C + b_{k + 1} a_{k + 1} = i = 1 \sum k + 1 b_{i} a_{i} .$ 故 $P (k + 1)$ 成立。结合基步，数学归纳法证明全部 $n \geq 2$ 。

易错点

把原权重直接用于前 $k$ 项而忘记它们的和小于1。
归纳假设只写一句“成立”，没有在归纳步实际使用。
对 $a_{i} = 0$ 直接取对数或除法。

小结

归纳步的关键是把 $k + 1$ 元问题压成一个已知的 $k$ 元问题和一个二元问题。

2015 江苏卷（数学Ⅱ附加题）第 23 题 · 解答

已知集合 $X = {1, 2, 3}$ ， $Y_{n} = {1, 2, 3, \dots, n}$ $(n \in N^{*})$ ，设 $S_{n} = ⎩ ⎨ ⎧ (a, b) a 整除 b 或 b 整除 a, a \in X, b \in Y_{n} ⎭ ⎬ ⎫ 。$ 令 $f (n)$ 表示集合 $S_{n}$ 所含元素的个数。 (2) 当 $n \geq 6$ 时，写出 $f (n)$ 的表达式，并用数学归纳法证明。

答案与解析

答案： $f (n) = n + ⌊ \frac{n}{2} ⌋ + ⌊ \frac{n}{3} ⌋ + 2$ （ $n \geq 6$ ）。

思路

从 $S_{k}$ 到 $S_{k + 1}$ 只新增第二个坐标等于 $k + 1$ 的有序数对，数清新增量就能完成归纳。

给出表达式与记号
记 $⌊ t ⌋$ 为不超过 $t$ 的最大整数。所求表达式为 $F (n) = n + ⌊ \frac{n}{2} ⌋ + ⌊ \frac{n}{3} ⌋ + 2.$ 以下证明 $f (n) = F (n)$ 对每个 $n \geq 6$ 成立。
验证基步 $n = 6$
$a = 1$ 时， $b$ 可取1至6，共6个； $a = 2$ 时， $b$ 为1、2、4、6，共4个； $a = 3$ 时， $b$ 为1、3、6，共3个。因此 $f (6) F (6) = 6 + 4 + 3 = 13, = 6 + 3 + 2 + 2 = 13,$ 基步成立。
写归纳假设并分析新增元素
假设某个 $k \geq 6$ 时 $f (k) = F (k)$ 。从 $S_{k}$ 到 $S_{k + 1}$ 只可能新增 $(1, k + 1)$ 、 $(2, k + 1)$ 、 $(3, k + 1)$ 。因 $k + 1 \geq 7$ 大于1、2、3，不可能由 $k + 1$ 整除 $a$ ；所以第一个新对必存在，第二个存在当且仅当2整除 $k + 1$ ，第三个存在当且仅当3整除 $k + 1$ 。
利用假设完成归纳步
记 $ε_{2}$ 在2整除 $k + 1$ 时为1，否则为0； $ε_{3}$ 同理。则 $f (k + 1) = f (k) + 1 + ε_{2} + ε_{3} .$ 另一方面， $⌊ \frac{k + 1}{j} ⌋ - ⌊ \frac{k}{j} ⌋$ 在 $j$ 整除 $k + 1$ 时为1，否则为0（ $j = 2, 3$ ），故 $F (k + 1) - F (k) = 1 + ε_{2} + ε_{3} .$ 由归纳假设得到 $f (k + 1) = F (k + 1)$ 。结合基步，所给表达式对全部 $n \geq 6$ 成立。

易错点

把 $a$ 整除 $b$ 与 $b$ 整除 $a$ 两个方向都满足的同一有序对重复计数。
归纳步新增第二坐标 $k + 1$ 时，又把旧元素重算一遍。
只列几个 $n$ 的结果而不完成 $k$ 到 $k + 1$ 。

小结

计数问题的归纳步可通过比较相邻两个集合新增了哪些元素来完成。