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)\) 的左式时，要意识到从 1 到 \(k+1\) 的和，简单来说就是从 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)\) 的左式开始：
\( \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)\) 的右式相符，因为将 \(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：整除性证明

在这类问题中，你需要证明一个表达式总是能被某个特定整数整除。

整除问题的“M”因子技巧

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

示例：证明 \( P(n): 7^n - 4^n \) 对所有整数 \(n \ge 1\) 均能被 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)\) 成立。

结论： 由于 \(P(1)\) 成立且 \(P(k) \implies P(k+1)\)，根据归纳法，\( 7^n - 4^n \) 对所有整数 \(n \ge 1\) 均能被 3 整除。

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

归纳法可用于证明一般的代数结果，包括涉及复数的结果。正如课程纲要 (FP2.4) 所规定，此单元中最著名的例子是证明棣莫弗定理（De Moivre’s Theorem）对正整数 \(n\) 成立。

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

预备知识： 你必须熟练三角和角公式：
\( \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)\) 的左式：
\( \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)\) 的右式。因此，\(P(k+1)\) 成立。

De Moivre 证明关键点： 结构很简单：拆开指数、代入 \(P(k)\)、展开、分组实部/虚部，最后利用和角公式简化。

避开常见陷阱

要让归纳法证明完全严谨，必须注意细节。以下是阅卷老师会检视的地方：

• 起点： 始终验证基本情况 \(n=1\)。如果命题仅对 \(n \ge 2\) 成立，则基本情况必须是 \(n=2\)。
• 标注清晰： 为你的三个步骤加上标签（基本情况、假设、归纳步骤）。
• 使用假设： 在 \(P(k+1)\) 步骤的代数推导中，你必须显式地使用 \(P(k)\) 的假设。如果不这样做，就不是数学归纳法证明。
• 结论陈述： 别忘了最后一定要写出引用数学归纳法原理 (PMI) 的总结句。