数学归纳法：证明与正整数有关命题的方法

多米诺骨牌的启示

想象一排多米诺骨牌，只要：

1. 第一张倒下（奠基）
2. 任意一张倒下能撞倒后一张（递推）

那么所有骨牌都会倒。数学归纳法正是把这一直觉变成严格的证明工具。

证明的两步

要证命题 $P(n)$ 对所有正整数 $n\ge n_0$ 成立：

第一步（奠基）：验证 $P(n_0)$ 成立

第二步（递推）：假设 $P(k)$ 成立（归纳假设，$k\ge n_0$），证明 $P(k+1)$ 成立

两步齐备，由归纳原理，$P(n)$ 对所有 $n\ge n_0$ 成立。

典例精析

例（证数列求和公式） 求证 $1+2+\cdots +n=\frac{n(n+1)}{2}$。

奠基：$n=1$ 时，左 $=1$，右 $=\frac{1\times 2}{2}=1$，成立。

递推：假设 $n=k$ 时成立，即 $1+2+\cdots +k=\frac{k(k+1)}{2}$。则 $n=k+1$ 时

$1+2+\cdots +k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}$

恰为 $n=k+1$ 时的公式。由数学归纳法，公式对所有正整数 $n$ 成立。$■$

辨析与提醒

• 两步缺一不可：只有奠基没有递推，无法传递；只有递推没有奠基，传递无起点。
• 必须用归纳假设：推 $n=k+1$ 时若没用到「$n=k$ 成立」，说明方法用错或归纳失效。
• 起点不一定是 1：命题从 $n=3$ 或 $n=5$ 开始，奠基就验那个起点。

跨学段衔接

小学「找规律」是归纳的萌芽（但只是猜想）；初中接触简单递推；高中数学归纳法把「猜想 → 证明」严格化；大学「强归纳法、结构归纳法」推广到更复杂的对象。数学归纳法是连接「有限验证」与「无穷结论」的桥梁，是离散数学的支柱。