第二数学归纳法

一句话

第二数学归纳法：

奠基： $P (1)$ 成立；
递推：假设 $P (1), P (2), \dots, P (k)$ 全部成立，推出 $P (k + 1)$ 成立。

那么 $P (n)$ 对一切正整数 $n$ 成立。

它和第一数学归纳法其实是一回事：令 $Q (n)$ 表示“ $P (1), \dots, P (n)$ 都成立”，对 $Q (n)$ 用第一数学归纳法就行了。区别只在用起来的感觉：推出下一块，可以借助前面任何一块，不必只是紧挨着的那块。 但要当心：如果 $P (k + 1)$ 用到的是 $P (k - 2)$ ，那么 $P (1), P (2), P (3)$ 就都得单独奠基——下面的格子会让你看见为什么。

例：3 分和 5 分的邮票能凑出 8 分以上的任何邮资

第 1 / 5 步

递推关系
能凑出 $n - 3$ 分，再贴一张 $3$ 分，就凑出 $n$ 分。所以 $P (n)$ 可以由 $P (n - 3)$ 推出——往回看的是三格之前，不是一格。格子按 $3$ 列排， $n - 3$ 正好在 $n$ 的正上方。

$P (n) \Leftarrow P (n - 3)$
一个起点不够
三列各要一个
写成第二归纳法
为什么 7 不行

先猜后证

只有 $4$ 分和 $7$ 分的邮票。从多少分起，任何邮资都能凑出？

分

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

一般地， $a, b$ 互素时，最大的凑不出的金额是 $ab - a - b$ （ $3 \cdot 5 - 3 - 5 = 7$ ， $4 \cdot 7 - 4 - 7 = 17$ ）。这个结论本身也可以用本站的办法验证。

第 1 站 · 代数：一项要用两个前项

已知 $x + \frac{1}{x}$ 是整数，证明对一切正整数 $n$ ， $x^{n} + \frac{1}{x ^{n}}$ 也是整数。

记 $s_{n} = x^{n} + x^{- n}$ 。只看 $s_{k}$ 推不出 $s_{k + 1}$ ，但下面这个恒等式同时用了 $s_{k}$ 和 $s_{k - 1}$ ：

例：x + 1/x 是整数

第 1 / 4 步

找关系
把 $s_{k}$ 和 $s_{1}$ 乘起来，正好多出一个 $s_{k - 1}$ 。

$s_{k} \cdot s_{1} = x^{k + 1} + x^{- (k + 1)} + x^{k - 1} + x^{- (k - 1)} = s_{k + 1} + s_{k - 1}$
递推式
两个起点
递推

第 2 站 · 数论：往回跳很远

每个大于 $1$ 的整数都能写成素数的乘积。

这里 $P (n)$ 要用的不是 $P (n - 1)$ ，而是“比 $n$ 小的某两个数”——到底是哪两个，事先不知道。这正是第二数学归纳法的用武之地。

例：素因数分解的存在性

第 1 / 4 步

奠基
$n = 2$ 是素数，它自己就是一个素数的乘积。

$2 = 2$
假设所有更小的
分两种情况
为什么第一归纳法不够

如果只奠基一个

Break it

反例实验室：去掉一个条件

结论： $a_{n} = 2^{n} + 1$ 对一切 $n$ 成立

$a_{1} = 3, a_{2} = 5, a_{n} = 3 a_{n - 1} - 2 a_{n - 2}$ 。递推：若 $a_{k - 1} = 2^{k - 1} + 1$ ， $a_{k} = 2^{k} + 1$ ，则 $a_{k + 1} = 3 \cdot 2^{k} + 3 - 2^{k} - 2 = 2^{k + 1} + 1$ 。两个起点都已设好。

练一练

练习 1基础

只有 $5$ 分和 $7$ 分的邮票。最大的凑不出的邮资是多少分？

练习 2基础

数列 $a_{1} = 1, a_{2} = 3, a_{n} = a_{n - 1} + 2 a_{n - 2} (n \geq 3)$ 。求 $a_{6}$ ，并用第二数学归纳法证明 $a_{n} \leq 2^{n}$ 。

练习 3提高

证明：每个正整数都能写成若干个互不相同的 $2$ 的幂之和（例如 $13 = 8 + 4 + 1$ ）。

练习 4挑战

已知 $x + \frac{1}{x} = 3$ ，求 $x^{5} + \frac{1}{x ^{5}}$ 。

一句话

例：3 分和 5 分的邮票能凑出 8 分以上的任何邮资

第 1 站 · 代数：一项要用两个前项

例：x + 1/x 是整数

第 2 站 · 数论：往回跳很远

例：素因数分解的存在性

如果只奠基一个

反例实验室：去掉一个条件

练一练

错误博物馆 · 本站展品

递推用了两个前项，却只奠基一个