Proof by induction

数学归纳法：征服无穷步骤

你好！欢迎学习进阶数学（Further Mathematics）中最优雅、最重要的证明方法之一：数学归纳法（Proof by Induction）。一旦掌握了这项技术，你就能证明对所有正整数成立的命题——这是一项真正强大的技能！

如果起初觉得有些复杂，也不必担心。数学归纳法遵循一套固定的逻辑结构。本质上，我们是在学习一种构建严密论证的“数学公式”。学完这些笔记后，你将能够把这一方法应用到求和、数列、整除性问题，甚至是复数运算的证明中！

什么是数学归纳法？（多米诺骨牌类比）

数学归纳法是一种用于证明命题 \(P(n)\) 对所有大于或等于起始整数（通常为 \(n=1\)）的整数 \(n\) 均成立的方法。

多米诺骨牌效应类比

想象你有一排无穷无尽的多米诺骨牌，编号为 1, 2, 3，以此类推。要证明所有骨牌都会倒下，你只需要证明两件事：

1. 基础步骤（第一推）： 你推倒了第一块骨牌（骨牌 1）。
2. 归纳步骤（连锁反应）： 你证明了如果任意一块骨牌（\(k\)）倒下，那么它的下一块骨牌（\(k+1\)）也一定会倒下。

如果这两点都成立，那么整排无穷的骨牌必定会全部倒下！

数学归纳法的三大核心步骤

每一个归纳法证明都必须严格遵循以下三个步骤。在考试中，请务必清晰地标出这些步骤！

步骤 1：基础步骤（\(n=1\)）

我们必须证明命题 \(P(n)\) 对最小的整数成立，通常是 \(n=1\)（根据题目要求，有时也可能是 \(n=0\) 或 \(n=2\)）。

• 将起始值（例如 \(n=1\)）代入命题的左边（LHS）。
• 将起始值代入命题的右边（RHS）。
• 得出结论：由于 LHS = RHS，因此 \(P(1)\) 成立。

步骤 2：归纳假设（\(n=k\)）

这是我们在骨牌链中设置假设性环节的地方。

• 我们假设命题 \(P(k)\) 对某个任意正整数 \(k\) 成立。
• 关键点：请清晰地写出命题 \(P(k)\) 的表达式。 你将在步骤 3 中用到这个等式。

常见错误提示： 学生有时会试图证明 \(P(k)\) 成立。请记住，你只需要假设它成立即可。证明过程在下一步！

步骤 3：归纳步骤（\(n=k+1\)）

现在，我们利用假设 \(P(k)\) 来证明下一个情况 \(P(k+1)\) 也必定成立。

• 写出你想要证明的命题 \(P(k+1)\)。
• 从 \(P(k+1)\) 的左边（LHS）开始推导。
• 通过代数变形，展示其中包含已知的假设 \(P(k)\)。
• 将 \(P(k)\) 的右边（RHS）代入你的表达式中。
• 化简最终表达式，直至其与 \(P(k+1)\) 的右边（RHS）完全一致。

最终结论： 完成步骤 3 后，你必须写出最终的结论陈述才能获得最后的分数。例如：“由于 \(P(1)\) 成立，且 \(P(k)\) 的成立蕴含 \(P(k+1)\) 的成立，根据数学归纳法原理，可知 \(P(n)\) 对所有正整数 \(n\) 均成立。”

应用类型 1：求和与级数

这是最常见的归纳证明类型，即证明级数求和的公式（例如算术级数、几何级数或使用 $\sum$ 符号表示的级数）。

求和问题的关键策略

处理 \(P(k+1)\) 的 LHS 时，要意识到前 \(k+1\) 项的和本质上就是前 \(k\) 项的和加上第 \((k+1)\) 项。

$$ \text{LHS of } P(k+1) = \sum_{r=1}^{k+1} f(r) = \left( \sum_{r=1}^{k} f(r) \right) + f(k+1) $$

括号部分正是你的归纳假设 \(P(k)\)！这就是你需要代入的地方。

示例：证明简单数列的求和：

证明对所有整数 \(n \ge 1\)，\( \sum_{r=1}^{n} r^2 = \frac{1}{6}n(n+1)(2n+1) \) 成立。

步骤 1：基础步骤（\(n=1\)）
LHS: \( \sum_{r=1}^{1} r^2 = 1^2 = 1 \)
RHS: \( \frac{1}{6}(1)(1+1)(2(1)+1) = \frac{1}{6}(1)(2)(3) = 1 \)
由于 LHS = RHS，因此 \(P(1)\) 成立。

步骤 2：假设（\(n=k\)）
假设 \(P(k)\) 对某个正整数 \(k\) 成立：
$$ \sum_{r=1}^{k} r^2 = \frac{1}{6}k(k+1)(2k+1) $$

步骤 3：归纳步骤（\(n=k+1\)）
我们想要证明 \(P(k+1)\) 成立。从 \(P(k+1)\) 的 LHS 开始：
$$ \text{LHS} = \sum_{r=1}^{k+1} r^2 = \left( \sum_{r=1}^{k} r^2 \right) + (k+1)^2 $$ 代入归纳假设 \(P(k)\)：
$$ \text{LHS} = \frac{1}{6}k(k+1)(2k+1) + (k+1)^2 $$ 提取公因式 \((k+1)\)：
$$ \text{LHS} = (k+1) \left[ \frac{1}{6}k(2k+1) + (k+1) \right] $$ $$ \text{LHS} = (k+1) \left[ \frac{2k^2+k}{6} + \frac{6(k+1)}{6} \right] $$ $$ \text{LHS} = \frac{1}{6}(k+1) \left[ 2k^2+k + 6k+6 \right] $$ $$ \text{LHS} = \frac{1}{6}(k+1) (2k^2+7k+6) $$ 对二次项 \(2k^2+7k+6\) 因式分解得到 \((k+2)(2k+3)\)：
$$ \text{LHS} = \frac{1}{6}(k+1)(k+2)(2k+3) $$ 这与 \(P(k+1)\) 的 RHS 一致，因为将 \(n\) 替换为 \(k+1\) 得到 \( \frac{1}{6}(k+1)((k+1)+1)(2(k+1)+1) = \frac{1}{6}(k+1)(k+2)(2k+3) \)。
因此，\(P(k+1)\) 成立。

求和问题的关键点： 始终寻找 \(P(k+1)\) 表达式内部的 \(P(k)\) 部分。因式分解是你简化代数过程中的好帮手。

应用类型 2：整除性证明

在这类问题中，要求证明某个表达式（通常涉及指数）总是能被某个整数整除。

教学大纲示例： 证明对所有正整数 \(n\)，\( 7^n + 4^{n+1} \) 能被 6 整除。

整除性的“M”因子技巧

当证明 \(f(n)\) 能被 \(M\) 整除时，步骤 3 的目标是通过变形 \(f(k+1)\)，使其一部分恰好是 \(f(k)\)，而剩余部分显然是 \(M\) 的倍数。

步骤 1：基础步骤（\(n=1\)）
\( 7^1 + 4^{1+1} = 7 + 4^2 = 7 + 16 = 23 \)。等等，23 不能被 6 整除！

小贴士： 务必检查题目背景。如果命题本身有误，你是无法证明它的！让我们修正这个示例为更具普适性的类型（整除性技巧演示）：证明 \( 7^n - 4^n \) 能被 3 整除。

证明对所有整数 \(n \ge 1\)，\( P(n): 7^n - 4^n \) 能被 3 整除。

步骤 1：基础步骤（\(n=1\)）
\( 7^1 - 4^1 = 3 \)。因为 3 能被 3 整除，所以 \(P(1)\) 成立。

步骤 2：假设（\(n=k\)）
假设 \(P(k)\) 对某个正整数 \(k\) 成立。即 \( 7^k - 4^k \) 能被 3 整除。我们可以写成：
$$ 7^k - 4^k = 3M $$ 其中 \(M\) 为某个整数。重写为：\( 7^k = 4^k + 3M \)。 (这种变换是解题关键！)

步骤 3：归纳步骤（\(n=k+1\)）
考察 \(P(k+1): 7^{k+1} - 4^{k+1}\)。
$$ 7^{k+1} - 4^{k+1} = 7 \cdot 7^k - 4 \cdot 4^k $$ 代入步骤 2 中假设的 \( 7^k \) 表达式：
$$ 7^{k+1} - 4^{k+1} = 7 (4^k + 3M) - 4 \cdot 4^k $$ 展开并重排，以分离出 3 的倍数：
$$ 7 \cdot 4^k + 7 \cdot 3M - 4 \cdot 4^k $$ 合并含 \(4^k\) 的项：
$$ (7-4) \cdot 4^k + 21M $$ $$ 3 \cdot 4^k + 21M $$ 提取公因数 3：
$$ 3 (4^k + 7M) $$ 由于 \(k\) 和 \(M\) 是整数，\((4^k + 7M)\) 也是整数。因此，\( 7^{k+1} - 4^{k+1} \) 是 3 的倍数。
因此，\(P(k+1)\) 成立。

结论： 通过归纳法，可知 \( 7^n - 4^n \) 对所有整数 \(n \ge 1\) 均能被 3 整除。

应用类型 3：代数与复数证明

归纳法可以用来证明通用的代数结果，包括涉及复数的结果。本模块中最著名的例子就是根据教学大纲（FP2.4）证明棣莫弗定理（De Moivre’s Theorem）对正整数 \(n\) 成立。

证明对所有正整数 \(n\)，\( P(n): (\cos \theta + i \sin \theta)^n = \cos n\theta + i \sin n\theta \) 成立。

必备知识： 你必须熟悉三角函数的和角公式：
\( \cos(A+B) = \cos A \cos B - \sin A \sin B \)
\( \sin(A+B) = \sin A \cos B + \cos A \sin B \)

步骤 1：基础步骤（\(n=1\)）
LHS: \( (\cos \theta + i \sin \theta)^1 = \cos \theta + i \sin \theta \)
RHS: \( \cos (1\theta) + i \sin (1\theta) = \cos \theta + i \sin \theta \)
由于 LHS = RHS，因此 \(P(1)\) 成立。

步骤 2：假设（\(n=k\)）
假设 \(P(k)\) 对某个正整数 \(k\) 成立：
$$ (\cos \theta + i \sin \theta)^k = \cos k\theta + i \sin k\theta $$

步骤 3：归纳步骤（\(n=k+1\)）
考察 \(P(k+1)\) 的 LHS：
$$ \text{LHS} = (\cos \theta + i \sin \theta)^{k+1} $$ 拆分指数：
$$ \text{LHS} = (\cos \theta + i \sin \theta)^k \cdot (\cos \theta + i \sin \theta)^1 $$ 代入归纳假设 \(P(k)\)：
$$ \text{LHS} = (\cos k\theta + i \sin k\theta) (\cos \theta + i \sin \theta) $$ 展开括号（如同复数乘法）：
$$ \text{LHS} = \cos k\theta \cos \theta + i \cos k\theta \sin \theta + i \sin k\theta \cos \theta + i^2 \sin k\theta \sin \theta $$ 因为 \(i^2 = -1\)，按实部和虚部分组：
$$ \text{LHS} = (\cos k\theta \cos \theta - \sin k\theta \sin \theta) + i (\sin k\theta \cos \theta + \cos k\theta \sin \theta) $$ 现在，应用三角和角公式（这是简化关键！）：
$$ \text{LHS} = \cos (k\theta + \theta) + i \sin (k\theta + \theta) $$ 提取 \(\theta\)：
$$ \text{LHS} = \cos ((k+1)\theta) + i \sin ((k+1)\theta) $$ 这正是 \(P(k+1)\) 的 RHS。因此，\(P(k+1)\) 成立。

棣莫弗定理证明要点： 结构非常简单：拆分指数、代入 \(P(k)\)、展开、分组实虚部，最后利用和角公式化简。

常见陷阱与避坑指南

为了确保归纳证明的严谨性，请注意以下细节，这些也是阅卷老师关注的重点：

• 起始点： 务必验证基础步骤 \(n=1\)。如果命题仅对 \(n \ge 2\) 成立，则基础步骤必须从 \(n=2\) 开始。
• 清晰标注： 请清楚标注三个步骤（基础步骤、假设、归纳步骤）。
• 使用假设： 在 \(P(k+1)\) 的代数运算中，必须显式地使用你的 \(P(k)\) 假设。如果不使用，就不算完整的数学归纳证明。
• 结论陈述： 不要忘记最后那句引用“数学归纳法原理（PMI）”的结论性陈述。