数学归纳法（Mathematical Induction）

核心定位

数学归纳法是证明与正整数（natural number）有关的命题的严格方法，其逻辑基础是皮亚诺公理（Peano axioms）中的归纳公理。本笔记从基本原理出发，系统阐述第一数学归纳法与第二数学归纳法（强归纳法），并连接 数列与微分方程核心方法、等差与等比数列的求和公式、通项与和的关系、幂和公式及推导 等数列核心板块。

---

一、数学归纳法的基本原理

1.1 第一数学归纳法（First Principle of Mathematical Induction）

第一数学归纳法（弱归纳法）

设 $P(n)$是一个与正整数$n$ 有关的命题。若满足以下两个条件：

1. 归纳奠基（Base Case）：$P(1)$（或 $P(n_0)$）成立。
2. 归纳递推（Inductive Step）：假设 $P(k)$ 成立（$k \ge 1$），能推出 $P(k+1)$ 也成立。

则 $P(n)$对所有正整数$n \ge 1$（或 $n \ge n_0$）成立。

逻辑结构：这相当于一个无限的「多米诺骨牌」推理链条： $$ P(1) \Rightarrow P(2) \Rightarrow P(3) \Rightarrow \cdots \Rightarrow P(n) \Rightarrow \cdots $$

归纳假设（Inductive Hypothesis）

在证明 $P(k+1)$时，假设$P(k)$成立，这个假设称为归纳假设。它是递推步骤的关键前提，不是循环论证——我们假设的是$k$时成立，要证明的是$k+1$ 时成立。

1.2 数学归纳法的逻辑等价性

数学归纳法等价于良序原理（Well-Ordering Principle）：正整数集的任意非空子集均有最小元。两者可以互相推导，都是皮亚诺公理体系的等价表述。

---

二、第二数学归纳法（强归纳法）

2.1 定义

第二数学归纳法（Strong Induction / Complete Induction）

设 $P(n)$是一个与正整数$n$ 有关的命题。若满足：

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

则 $P(n)$对所有正整数$n$ 成立。

2.2 与第一归纳法的区别

	第一数学归纳法	第二数学归纳法（强归纳法）
归纳假设的范围	仅假设 $P(k)$成立	假设$P(1), P(2), \dots, P(k)$ 全部成立
适用场景	当前项仅依赖前一项	当前项依赖前面多项（如递推数列）
证明难度	通常更简单	假设更强，有时反而更易证明

选择策略

• 若 $P(k+1)$的证明只需要$P(k)$，用第一归纳法即可。
• 若 $P(k+1)$的证明需要用到$P(1), P(2), \dots, P(k)$中的多个（如斐波那契递推$F_{k+1} = F_k + F_{k-1}$），必须使用第二归纳法（强归纳法）。

2.3 两种归纳法的等价性

第一数学归纳法与第二数学归纳法在皮亚诺公理体系下是等价的——可以通过良序原理证明两者的互相推导关系。在实际使用中，选择更方便的一种即可。

---

三、典型例题

3.1 等差数列求和公式证明

例 1：等差数列前 $n$ 项和

证明：$1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$。

证明（第一数学归纳法）：

• 奠基 $n=1$：左边 $=1$，右边 $= \dfrac{1 \times 2}{2} = 1$，成立。
• 归纳假设：设 $n=k$时命题成立，即$1+2+\cdots+k = \dfrac{k(k+1)}{2}$。
• 归纳递推 $n=k+1$： $$ \begin{aligned} 1+2+\cdots+k+(k+1) &= \frac{k(k+1)}{2} + (k+1) \newline &= \frac{k(k+1) + 2(k+1)}{2} \newline &= \frac{(k+1)(k+2)}{2}. \end{aligned} $$ 右边 $\dfrac{(k+1)[(k+1)+1]}{2}$恰为$n=k+1$ 时的公式形式，证毕。

例 2：等比数列前 $n$ 项和

证明：对于 $q \neq 1$，$a_1 + a_1 q + a_1 q^2 + \cdots + a_1 q^{n-1} = \dfrac{a_1(1-q^n)}{1-q}$。

证明（第一数学归纳法）：

• 奠基 $n=1$：左边 $=a_1$，右边 $= \dfrac{a_1(1-q)}{1-q} = a_1$，成立。
• 归纳假设：设 $n=k$时命题成立，即$S_k = \dfrac{a_1(1-q^k)}{1-q}$。
• 归纳递推 $n=k+1$： $$ \begin{aligned} S_{k+1} = S_k + a_1 q^k &= \frac{a_1(1-q^k)}{1-q} + a_1 q^k \newline &= \frac{a_1(1-q^k) + a_1 q^k (1-q)}{1-q} \newline &= \frac{a_1(1 - q^k + q^k - q^{k+1})}{1-q} \newline &= \frac{a_1(1 - q^{k+1})}{1-q}. \end{aligned} $$ 证毕。

与 等差与等比数列的求和公式 的关系

该笔记从倒序相加法和错位相减法直接推导求和公式，而归纳法则提供了对公式正确性的严格验证。两方法互补：推导用构造法，验证用归纳法。

3.2 整除性证明

例 3：$n^3 - n$被$6$ 整除

证明：对任意正整数 $n$，$n^3 - n$能被$6$ 整除。

证明（第一数学归纳法）：

• 奠基 $n=1$：$1^3 - 1 = 0$，$6 \mid 0$，成立。
• 归纳假设：设 $n=k$时$k^3 - k$能被$6$ 整除。
• 归纳递推 $n=k+1$： $$ \begin{aligned} (k+1)^3 - (k+1) &= (k^3 + 3k^2 + 3k + 1) - k - 1 \newline &= (k^3 - k) + 3k(k+1). \end{aligned} $$ 由归纳假设，$k^3 - k$能被$6$ 整除；$k(k+1)$是连续两整数之积，必为偶数，故$3k(k+1)$能被$6$整除。两项之和能被$6$ 整除，证毕。

例 4：$4^{n} - 1$被$3$ 整除

证明：对任意正整数 $n$，$4^n - 1$能被$3$ 整除。

证明（第一数学归纳法）：

• 奠基 $n=1$：$4^1 - 1 = 3$，$3 \mid 3$，成立。
• 归纳假设：设 $n=k$时$4^k - 1 = 3m$（$m \in \mathbb{Z}$）。
• 归纳递推 $n=k+1$： $$ \begin{aligned} 4^{k+1} - 1 &= 4 \cdot 4^k - 1 = 4(3m + 1) - 1 \newline &= 12m + 4 - 1 = 12m + 3 = 3(4m + 1), \end{aligned} $$ 能被 $3$ 整除，证毕。

3.3 不等式证明

例 5：伯努利不等式（Bernoulli's Inequality）

证明：对任意 $x > -1$且$x \neq 0$，正整数 $n \ge 2$，有 $(1+x)^n > 1 + nx$。

证明（第一数学归纳法）：

• 奠基 $n=2$：$(1+x)^2 = 1 + 2x + x^2 > 1 + 2x$（因为 $x^2 > 0$），成立。
• 归纳假设：设 $n=k$（$k \ge 2$）时 $(1+x)^k > 1 + kx$。
• 归纳递推 $n=k+1$： $$ \begin{aligned} (1+x)^{k+1} &= (1+x)^k (1+x) \newline &> (1 + kx)(1 + x) \quad \text{（归纳假设，且 $1+x > 0$）} \newline &= 1 + (k+1)x + kx^2 \newline &> 1 + (k+1)x \quad \text{（$kx^2 > 0$）}. \end{aligned} $$ 证毕。

例 6：$2^n > n^2$对$n \ge 5$ 成立

证明：当 $n \ge 5$ 时，$2^n > n^2$。

证明（第一数学归纳法）：

• 奠基 $n=5$：$2^5 = 32 > 25 = 5^2$，成立。
• 归纳假设：设 $n=k$（$k \ge 5$）时 $2^k > k^2$。
• 归纳递推 $n=k+1$： $$ \begin{aligned} 2^{k+1} &= 2 \cdot 2^k > 2 k^2 \quad \text{（归纳假设）} \newline &= k^2 + k^2 \ge k^2 + 5k \quad \text{（$k \ge 5$）} \newline &= k^2 + 2k + 3k > k^2 + 2k + 1 = (k+1)^2. \end{aligned} $$ 证毕。

不等式归纳中的易错点

在放缩过程中必须确保不等号方向一致，且每一步放缩都要有充分理由。特别要注意归纳假设条件 $1+x > 0$ 这类隐含前提。

3.4 递推数列通项证明

例 7：一阶线性递推

已知 $a_1 = 2$，$a_{n+1} = 3a_n + 1$，证明 $a_n = \dfrac{5 \cdot 3^{n-1} - 1}{2}$。

证明（第一数学归纳法）：

• 奠基 $n=1$：$a_1 = \dfrac{5 \cdot 3^0 - 1}{2} = \dfrac{4}{2} = 2$，成立。
• 归纳假设：设 $n=k$时$a_k = \dfrac{5 \cdot 3^{k-1} - 1}{2}$。
• 归纳递推 $n=k+1$： $$ \begin{aligned} a_{k+1} &= 3a_k + 1 = 3 \cdot \frac{5 \cdot 3^{k-1} - 1}{2} + 1 \newline &= \frac{5 \cdot 3^{k} - 3}{2} + \frac{2}{2} = \frac{5 \cdot 3^{k} - 1}{2}, \end{aligned} $$ 恰为 $n=k+1$ 时的通项公式形式，证毕。

归纳法 vs 其他求通项方法

递推数列通项的推导常用特征根法、不动点法等（见 数列与微分方程核心方法），但归纳法可用于验证推导出的通项公式是否正确。先猜后证（guess and verify）是数学中常见的策略。

---

四、归纳法在斐波那契数列中的应用

斐波那契数列的递推 $F_n = F_{n-1} + F_{n-2}$（$n \ge 3$）涉及前两项，因此许多性质需要**第二数学归纳法（强归纳法）**来证明。

例 8：斐波那契数列的上界

证明斐波那契数列满足 $F_n < 2^n$对所有$n \ge 1$ 成立。

证明（第二数学归纳法）：

• 奠基：$F_1 = 1 < 2^1 = 2$，$F_2 = 1 < 2^2 = 4$，成立。
• 归纳假设：假设对所有 $i \le k$（$k \ge 2$），$F_i < 2^i$ 成立。
• 归纳递推 $n=k+1$： $$ F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} = 3 \cdot 2^{k-1} < 4 \cdot 2^{k-1} = 2^{k+1}. $$ 证毕。

例 9：卡西尼恒等式（Cassini's Identity）

证明 $F_{n-1} F_{n+1} - F_n^2 = (-1)^n$（$n \ge 2$）。

证明（第一数学归纳法，利用递推消去 $F_{n+1}$）：

• 奠基 $n=2$：$F_1 F_3 - F_2^2 = 1 \times 2 - 1^2 = 1 = (-1)^2$，成立。
• 归纳假设：设 $n=k$时$F_{k-1} F_{k+1} - F_k^2 = (-1)^k$。
• 归纳递推 $n=k+1$： $$ \begin{aligned} F_k F_{k+2} - F_{k+1}^2 &= F_k(F_{k+1} + F_k) - F_{k+1}^2 \newline &= F_k F_{k+1} + F_k^2 - F_{k+1}^2 \newline &= F_k^2 + F_{k+1}(F_k - F_{k+1}) \newline &= F_k^2 + F_{k+1}(-F_{k-1}) \newline &= F_k^2 - F_{k-1}F_{k+1} = -(-1)^k = (-1)^{k+1}. \end{aligned} $$ 证毕。

更多斐波那契性质

关于 Binet 公式的完整推导及斐波那契数列的更多性质，参见 斐波那契数列的通项公式推导。

---

五、归纳法的注意事项与常见错误

5.1 常见错误

错误 1：缺少奠基步骤

只做归纳递推而不验证奠基步骤，导致多米诺骨牌没有「第一张牌」。例如，试图证明「所有正整数都相等」时，如果省略奠基步骤，归纳递推看似成立但实际上命题为假。

错误 2：归纳假设使用不当

在需要第二归纳法（强归纳法）的场景下仅使用第一归纳法的假设（只假设 $P(k)$），导致无法证明 $P(k+1)$。

• 典型场景：斐波那契类型的递推 $P(k+1)$依赖$P(k)$和$P(k-1)$，此时必须使用强归纳法。

错误 3：循环论证（Circular Reasoning）

在证明 $P(k+1)$时，暗中假定$P(k+1)$ 本身或其等价形式成立——这构成循环论证，证明无效。

错误 4：归纳递推不适用所有 $k$

递推步骤必须对所有 $k \ge n_0$成立。若递推仅对部分$k$成立（例如需要$k$ 为偶数），则归纳链断裂，证明无效。

5.2 归纳法的局限性

• 数学归纳法只能证明命题的真假，不能发现新的公式或结论——发现需要归纳推理（inductive reasoning，即从特例猜测一般规律），然后通过数学归纳法（mathematical induction）严格证明。
• 归纳法仅适用于与正整数（或可数良序集）相关的命题，不能直接用于实数连续统上的命题。

归纳法的「先猜后证」策略

在实际问题中，通常先计算 $n=1,2,3,4$ 的特例，观察规律猜测通项公式，再用数学归纳法严格证明。这一策略广泛用于数列求和与递推问题（参见 幂和公式及推导 中的待定系数法与归纳验证）。

---

六、知识图谱

知识图谱入口

• 数列与微分方程核心方法 → 数列与微分方程核心方法：特征根法、不动点法推导通项，归纳法用于验证
• 斐波那契数列 → 斐波那契数列的通项公式推导：Binet 公式的推导及强归纳法的典型应用
• 幂和公式 → 幂和公式及推导：裂项相消推导幂和公式，归纳法提供严格验证
• 等差与等比数列求和 → 等差与等比数列的求和公式：求和公式的归纳法证明
• 通项与和的关系 → 通项与和的关系：从 $S_n$与$a_n$ 的混合关系导出递推，归纳法验证通项