数学归纳法原理

数学归纳法是一种严谨的证明方法，专门用于证明与正整数有关的命题。理解它的原理，就能掌握一种强大的证明工具。

基本原理

数学归纳法

要证明命题 $P(n)$ 对所有正整数 $n \geq n_0$ 成立，只需证明：

1. 基础步骤：$P(n_0)$ 成立
2. 归纳步骤：假设 $P(k)$ 成立（归纳假设），证明 $P(k+1)$ 也成立

证明步骤

使用数学归纳法证明命题的标准步骤：

步骤1：基础步骤（Base Case）

验证命题对初始值 $n = n_0$（通常是1）成立。

示例：证明 $P(1)$ 成立

步骤2：归纳假设（Inductive Hypothesis）

假设命题对 $n = k$（$k \geq n_0$）成立。

示例：假设 $P(k)$ 成立

步骤3：归纳步骤（Inductive Step）

在归纳假设的基础上，证明命题对 $n = k+1$ 也成立。

示例：利用 $P(k)$ 成立，证明 $P(k+1)$ 成立

步骤4：结论

由数学归纳法原理，命题对所有 $n \geq n_0$ 成立。

为什么数学归纳法是有效的？

数学归纳法的有效性基于自然数的良序性：每个非空的自然数集合都有最小元素。

假设命题 $P(n)$ 不是对所有 $n \geq n_0$ 都成立，那么存在一个最小的 $m > n_0$ 使得 $P(m)$ 不成立。

但是：

• $P(n_0)$ 成立（基础步骤）
• $P(m-1)$ 成立（因为 $m$ 是最小的反例）
• 由归纳步骤，$P(m)$ 应该成立

这产生了矛盾！所以命题对所有 $n \geq n_0$ 都成立。

这就是为什么两个步骤缺一不可：

• 没有基础步骤，第一块骨牌不会倒
• 没有归纳步骤，骨牌之间没有连锁反应

简单示例

示例1：证明求和公式

命题：证明 $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ 对所有正整数 $n$ 成立。

证明：

基础步骤：当 $n = 1$ 时， $\text{左边} = 1, \quad \text{右边} = \frac{1 \times 2}{2} = 1$ 等式成立。

归纳假设：假设当 $n = k$ 时等式成立，即 $1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$

归纳步骤：证明当 $n = k+1$ 时等式也成立。

$$\begin{aligned} 1 + 2 + 3 + \cdots + k + (k+1) &= \frac{k(k+1)}{2} + (k+1) \quad \text{（使用归纳假设）} \\ &= \frac{k(k+1) + 2(k+1)}{2} \\ &= \frac{(k+1)(k+2)}{2} \\ &= \frac{(k+1)[(k+1)+1]}{2} \end{aligned}$$

这正是 $n = k+1$ 时的公式形式。

结论：由数学归纳法，等式对所有正整数 $n$ 成立。

示例2：证明幂次公式

命题：证明 $2^n > n$ 对所有正整数 $n$ 成立。

证明：

基础步骤：当 $n = 1$ 时，$2^1 = 2 > 1$，成立。

归纳假设：假设 $2^k > k$。

归纳步骤：

$$\begin{aligned} 2^{k+1} &= 2 \cdot 2^k \\ &> 2k \quad \text{（使用归纳假设）} \\ &> k + 1 \quad \text{（因为 $k \geq 1$ 时，$2k \geq k+1$）} \end{aligned}$$

结论：由数学归纳法，$2^n > n$ 对所有正整数 $n$ 成立。

常见错误

练习题

练习 1

用数学归纳法证明：$1 + 3 + 5 + \cdots + (2n-1) = n^2$

参考答案

证明：

基础步骤：$n = 1$ 时，左边 $= 1$，右边 $= 1^2 = 1$，成立。

归纳假设：假设 $n = k$ 时成立，即 $1 + 3 + 5 + \cdots + (2k-1) = k^2$

归纳步骤：

$$\begin{aligned} &1 + 3 + 5 + \cdots + (2k-1) + (2(k+1)-1) \\ &= k^2 + (2k+1) \\ &= k^2 + 2k + 1 \\ &= (k+1)^2 \end{aligned}$$

结论：由数学归纳法，等式对所有正整数 $n$ 成立。

练习 2

用数学归纳法证明：$1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$

参考答案

证明：

基础步骤：$n = 1$ 时，左边 $= 1$，右边 $= \frac{1 \times 2 \times 3}{6} = 1$，成立。

归纳假设：假设 $n = k$ 时成立。

归纳步骤：

$$\begin{aligned} &1^2 + 2^2 + \cdots + k^2 + (k+1)^2 \\ &= \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \\ &= \frac{k(k+1)(2k+1) + 6(k+1)^2}{6} \\ &= \frac{(k+1)[k(2k+1) + 6(k+1)]}{6} \\ &= \frac{(k+1)(2k^2 + 7k + 6)}{6} \\ &= \frac{(k+1)(k+2)(2k+3)}{6} \\ &= \frac{(k+1)[(k+1)+1][2(k+1)+1]}{6} \end{aligned}$$

结论：由数学归纳法，等式成立。

练习 3

用数学归纳法证明：$3^n > 2n + 1$ 对所有 $n \geq 1$ 成立。

参考答案

证明：

基础步骤：$n = 1$ 时，$3^1 = 3 > 2 \times 1 + 1 = 3$… 不对，应该是 $3 \not> 3$。

让我们从 $n = 2$ 开始：$3^2 = 9 > 2 \times 2 + 1 = 5$，成立。

归纳假设：假设 $3^k > 2k + 1$。

归纳步骤：

$$\begin{aligned} 3^{k+1} &= 3 \cdot 3^k \\ &> 3(2k + 1) \quad \text{（归纳假设）} \\ &= 6k + 3 \\ &> 2k + 3 \quad \text{（因为 $k \geq 2$ 时，$6k > 2k$）} \\ &= 2(k+1) + 1 \end{aligned}$$

结论：由数学归纳法，不等式对所有 $n \geq 2$ 成立。

---

总结

本文出现的符号

符号	类型	读音/说明	在本文中的含义
$P(n)$	命题	P of n	关于 $n$ 的命题
$n_0$	常数	n sub 0	初始值
$k$	变量	k	归纳假设中的变量

中英对照

中文术语	英文术语	音标	说明
数学归纳法	mathematical induction	/ˌmæθəˈmætɪkəl ɪnˈdʌkʃən/	证明与自然数有关命题的方法
基础步骤	base case	/beɪs keɪs/	验证初始情况
归纳假设	inductive hypothesis	/ɪnˈdʌktɪv haɪˈpɒθəsɪs/	假设命题对 $n=k$ 成立
归纳步骤	inductive step	/ɪnˈdʌktɪv step/	从 $n=k$ 推导到 $n=k+1$

下一章节 证明等式