第一数学归纳法

一句话

要证明一串命题 $P(1),P(2),P(3),\dots$ 全部成立，只需做两件事：

1. 奠基：验证 $P(1)$ 成立——推倒第一块骨牌。
2. 递推：假设 $P(k)$ 成立（归纳假设），由它推出 $P(k+1)$ 成立——证明每一块倒下都会碰倒下一块。

两件事都做到了，$P(n)$ 就对一切正整数 $n$ 成立。这就是第一数学归纳法。它的根据是正整数的一条基本性质（归纳公理）：一个正整数的集合，如果含有 $1$，并且含有 $n$ 就一定含有 $n+1$，那它就是全体正整数。

注意第 2 步证的是一个蕴含式“如果 $P(k)$，那么 $P(k+1)$”，而不是 $P(k+1)$ 本身。我们不必知道第 $k$ 块骨牌此刻倒没倒，只要保证：它一倒，下一块必倒。

归纳法不必从 $1$ 开始：从 $n_0$ 奠基，对 $k\ge n_0$ 递推，结论就是“对一切 $n\ge n_0$ 成立”。

第 1 站 · 整除

对一切正整数 $n$，$3\mid n^3+2n$。

第 2 站 · 计数

$n$ 个元素的集合恰有 $2^n$ 个子集。 这里的“递推”是一个构造：从 $k$ 个元素到 $k+1$ 个元素，子集是怎么增多的？

“添一个新元素、看看多出来什么”是组合问题里最常见的递推方式。

第 3 站 · 不等式：起点和跨度要配好

伯努利不等式：当 $x>-1$ 时，对一切正整数 $n$，$(1+x{)}^n\ge 1+nx$。

如果没有 $x>-1$，第二步乘的可能是负数，不等号会反向——链条在这里断了。比如 $x=-3$，$n=3$：$(1-3{)}^3=-8$，而 $1+3\cdot (-3)=-8$，还相等；$n=2$ 时 $(-2{)}^2=4\ge -5$ 也对；可是 $x=-3$，$n=5$：$(-2{)}^5=-32<1-15=-14$，不等式错了。

如果第一块没推

练一练