数学归纳法

一句话

设 $P (n)$ 是关于正整数 $n$ 的命题。如果

基础： $P (n_{0})$ 成立；
递推：只要 $P (k)$ 成立（ $k \geq n_{0}$ ），就能推出 $P (k + 1)$ 成立，

那么 $P (n)$ 对一切 $n \geq n_{0}$ 成立。这就像一排多米诺骨牌：第一块倒下，每一块又都能碰倒下一块，于是全部倒下。

光“验证了很多个”是不够的。上面的图里， $n^{2} + n + 41$ 从 $n = 1$ 到 $39$ 全是质数，到 $40$ 却是 $4 1^{2}$ 。

例：1 + 3 + 5 + … + (2n − 1) = n²

第 1 / 4 步

基础
$n = 1$ ：左边 $1$ ，右边 $1^{2} = 1$ ，成立。第一块能推倒。

$1 = 1^{2}$
归纳假设
递推
全部倒下

先猜后证

命题 $2^{n} > n^{2}$ 。从哪一个 $n_{0}$ 起，它对所有 $n \geq n_{0}$ 都成立（取最小的 $n_{0}$ ）？

先选定答案，才能看到结论。

第 1 站 · 第二数学归纳法（卷五）

递推式牵涉前两项时，只假设 $P (k)$ 不够用，要假设 $P (k)$ 和 $P (k - 1)$ 都成立——基础也要验两个。

例：a₁ = 1，a₂ = 3，aₙ₊₂ = 3aₙ₊₁ − 2aₙ。证明 aₙ = 2ⁿ − 1

第 1 / 4 步

基础：两块
$a_{1} = 1 = 2^{1} - 1$ ， $a_{2} = 3 = 2^{2} - 1$ 。

$a_{1} = 2^{1} - 1, a_{2} = 2^{2} - 1$
假设前两项
推出下一项
结论

第 2 站 · 选择适当的跨度（卷五）

不一定非要从 $k$ 推到 $k + 1$ 。如果从 $k$ 推到 $k + 3$ 更自然，就跨 $3$ 步——只是要准备 $3$ 个起点。

例：任何 n ≥ 8 分的邮资都能用 3 分和 5 分邮票凑出

第 1 / 4 步

跨度选 3
能凑出 $k$ 分，再贴一张 $3$ 分就是 $k + 3$ 分。递推一次跨 $3$ 。

$P (k) \Rightarrow P (k + 3)$
三个基础
三条链
为什么从 8 开始

第 3 站 · 加强命题（卷五）

有时候原命题“太弱”，归纳假设给的信息不够推下去；证一个更强的命题反而顺利。

一题多解

证明：对一切正整数 $n$ ， $1 + \frac{1}{2 ^{2}} + \frac{1}{3 ^{2}} + \dots + \frac{1}{n ^{2}} < 2$ 。

直接归纳：推不动

假设 $S_{k} < 2$ ，那么 $S_{k + 1} = S_{k} + \frac{1}{( k + 1 ) ^{2}} < 2 + \frac{1}{( k + 1 ) ^{2}}$ 。

右边比 $2$ 大，什么也推不出。问题在于：“ $< 2$ ”没有告诉我们离 $2$ 还有多远。

代价假设只说“小于 2”，加上一项后就不知道了。

加强为 S_n ≤ 2 − 1/n

$n = 1$ ： $1 \leq 2 - 1$ ，成立。假设 $S_{k} \leq 2 - \frac{1}{k}$ ，则

$S_{k + 1} \leq 2 - \frac{1}{k} + \frac{1}{( k + 1 ) ^{2}} \leq 2 - \frac{1}{k} + \frac{1}{k ( k + 1 )} = 2 - \frac{1}{k + 1} .$

这里用到 $\frac{1}{( k + 1 ) ^{2}} < \frac{1}{k ( k + 1 )} = \frac{1}{k} - \frac{1}{k + 1}$ 。于是 $S_{n} \leq 2 - \frac{1}{n} < 2$ 。

代价命题更强，但假设也更强，正好够用。

第 4 站 · 均值不等式的证明（卷六）

柯西的“向前—向后归纳法”：先沿 $2, 4, 8, \dots$ 跳着走，再往回一步一步补上中间的 $n$ 。

例：证明 n 个正数的算术平均 ≥ 几何平均

第 1 / 4 步

基础 n = 2
$\frac{a + b}{2} \geq ab$ ，等价于 $(a - b)^{2} \geq 0$ 。

$\frac{a + b}{2} \geq ab$
向前：n → 2n
向后：n → n − 1
全部覆盖

练一练

练习 1基础

用 $3$ 分和 $5$ 分的邮票（数量不限），凑不出的最大邮资是多少分？

练习 2基础

使得 $n^{2} < 2^{n}$ 对一切 $n \geq N$ 成立的最小正整数 $N$ 是多少？

练习 3提高

证明：对一切正整数 $n$ ， $1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} < 2 n$ 。

练习 4挑战

已知 $a_{1} = 1$ ， $a_{n + 1} = a_{n} + \frac{1}{a _{n}}$ 。证明：对一切正整数 $n$ ， $a_{n} \geq 2 n - 1$ 。

一句话

例：1 + 3 + 5 + … + (2n − 1) = n²

第 1 站 · 第二数学归纳法（卷五）

例：a₁ = 1，a₂ = 3，aₙ₊₂ = 3aₙ₊₁ − 2aₙ。证明 aₙ = 2ⁿ − 1

第 2 站 · 选择适当的跨度（卷五）

例：任何 n ≥ 8 分的邮资都能用 3 分和 5 分邮票凑出

第 3 站 · 加强命题（卷五）

直接归纳：推不动

加强为 S_n ≤ 2 − 1/n

第 4 站 · 均值不等式的证明（卷六）

例：证明 n 个正数的算术平均 ≥ 几何平均

练一练

错误博物馆 · 本站展品

只证了递推，没验证基础

跨度是 3，基础只验了一个

这条线路经过的站