Proof

欢迎来到数学归纳法（Mathematical Proof）的世界！

在过去的数学学习中，你可能已经注意到某些规律适用于你尝试过的每一个数字。但在进阶纯数学 1 (Further Pure Mathematics 1, FP1) 中，「看起来好像对」是不够的！我们需要达到 100% 的确定性。本章重点介绍数学归纳法（Mathematical Induction）——这是一种强大的技巧，用于证明一个命题对每一个正整数（\(n = 1, 2, 3, ...\)）都成立，而无需逐一检查（那样做永远也检查不完！）。

为什么这很重要？
把它想像成一排无穷无尽的骨牌。如果你能证明第一块骨牌会倒下，并且能证明「如果」任何一块骨牌倒下，它「一定」会推倒下一块，那么你就确信队列中的每一块骨牌最终都会倒下。这就是归纳法的核心所在！

你知道吗？
数学归纳法早在 10 世纪就已被使用，但在 19 世纪才被正式发展完善。它是计算机科学和进阶逻辑中证明公式的「黄金标准」。

预备知识快速复习：
• 整数（Integers）： 整数（我们通常专注于正整数，\(n \in \mathbb{Z}^+\)）。
• 级数求和（Summation, \(\sum\)）： 一种将数列相加的简写形式。
• 矩阵（Matrices）： 数字方阵（将在本章最后部分用到）。

1. 数学归纳法证明四步曲

如果刚开始觉得有点复杂，别担心！每一个归纳法证明都遵循完全相同的「食谱」。只要学会这四个步骤，本章中几乎所有的问题你都能迎刃而解。

步骤 1：基础步骤（Basis Step）
展示命题对于第一个情况（通常是 \(n = 1\)）成立。这就像检查你是否能推倒第一块骨牌。

步骤 2：归纳假设（Assumption）
假设命题对于某个任意数 \(k\) 成立。我们写作：「假设当 \(n = k\) 时命题成立」。

步骤 3：归纳步骤（Inductive Step）
这是证明的「引擎」。利用你在步骤 2 的假设，去证明该命题对于下一个数字 \(n = k + 1\) 也成立。这就像证明如果第 \(k\) 块骨牌倒下，第 \(k+1\) 块骨牌也一定会倒下。

步骤 4：结论（Conclusion）
你必须写下一个正式的结论句。这就像一个完美的「收尾」，把一切连接起来。

常见错误（要避免！）： 许多学生会忘记步骤 1！没有基础步骤，即使你证明了「如果它是对的，那么下一个也是对的」，但如果第一块骨牌永远没有倒下，整个证明就毫无意义了。

2. 级数求和的证明

归纳法在 FP1 中最常见的用途之一是证明求和公式。

例子： 证明 \(\sum_{r=1}^{n} r = \frac{1}{2}n(n+1)\)。
（注：这是将从 1 到 \(n\) 的所有数字相加的公式。）

步骤 1 (基础)： 令 \(n = 1\)。
LHS (左式) = 1。
RHS (右式) = \(\frac{1}{2}(1)(1 + 1) = 1\)。
LHS = RHS，因此对 \(n = 1\) 成立。

步骤 2 (假设)： 假设公式对 \(n = k\) 成立：
\(\sum_{r=1}^{k} r = \frac{1}{2}k(k+1)\)。

步骤 3 (归纳)： 我们要证明它对 \(n = k + 1\) 也成立。
到 \(k+1\) 的和等于到 \(k\) 的和加上下一项 (\(k+1\))：
\(\sum_{r=1}^{k+1} r = [\sum_{r=1}^{k} r] + (k+1)\)
代入步骤 2 的假设：
\(= \frac{1}{2}k(k+1) + (k+1)\)
现在，提取公因式 \((k+1)\)：
\(= (k+1)[\frac{1}{2}k + 1]\)
\(= (k+1)[\frac{k + 2}{2}]\)
\(= \frac{1}{2}(k+1)(k+2)\)
这正是原始公式，只是把 \(n\) 换成了 \((k+1)\)。成功！

步骤 4 (结论)： 「由于结果对 \(n=1\) 成立，且若对 \(n=k\) 成立亦能推导出对 \(n=k+1\) 成立，根据数学归纳法，该结果对所有 \(n \in \mathbb{Z}^+\) 皆成立。」

关键点： 做级数证明时，目标始终是将第 \((k+1)\) 项加到你的假设上，并透过代数运算（通常是因式分解）使结果看起来符合目标公式。

3. 整除性的证明

你可能会被要求证明像 \(3^{2n} + 11\) 这样的表达式总能被某个数（在此例中为 4）整除。

技巧： 在归纳步骤中，观察 \(f(k+1)\) 的表达式，试着将其拆解为「你知道能被整除的部分」（来自你的假设）和「显然能被整除的另一部分」。

范例解析：
1. 检查 \(n=1\)： \(3^{2(1)} + 11 = 9 + 11 = 20\)。因为 20 是 \(4 \times 5\)，所以对 \(n=1\) 成立。
2. 假设 \(n=k\)： 假设 \(3^{2k} + 11 = 4M\)（其中 \(M\) 为某个整数）。
3. 检查 \(n=k+1\)： \(f(k+1) = 3^{2(k+1)} + 11 = 3^{2k+2} + 11\)。
利用幂运算法则：\(3^{2k} \cdot 3^2 + 11 = 9(3^{2k}) + 11\)。
将 9 拆解为 \((8 + 1)\)：
\(= (8 \cdot 3^{2k}) + (1 \cdot 3^{2k} + 11)\)。
第一部分 (\(8 \cdot 3^{2k}\)) 显然能被 4 整除。第二部分 (\(3^{2k} + 11\)) 因为我们步骤 2 的假设，也能被 4 整除！因此，整个表达式都能被 4 整除。

记忆小撇步： 对于整除性问题，记得「拆解与代入」。将带有幂次的项拆开以匹配你的假设。

4. 数列通项的求法

有时你会得到一个递推关系式（其中每一项取决于前一项，例如 \(u_{n+1} = 3u_n + 4\)）和一个「通项」公式（\(u_n = 3^n - 2\)）。你需要用归纳法来证明该通项公式是正确的。

处理方法：
在归纳步骤中，从递推关系式 \(u_{k+1} = 3u_k + 4\) 开始。然后，将 \(u_k\) 替换为你假设的公式，进行简化，看看能否得到 \(u_{k+1}\) 的公式。

5. 矩阵乘积

这是考试的热门考点！你可能会被要求证明矩阵幂次的公式，例如 \( \mathbf{A}^n \)。

预备知识检查： 还记得如何进行 \(2 \times 2\) 矩阵乘法吗？是用「横列乘直行」（Row by Column）。

矩阵的归纳步骤：
要找出 \(\mathbf{A}^{k+1}\)，只需计算 \(\mathbf{A}^k \times \mathbf{A}\)。
1. 将 \(\mathbf{A}^k\) 替换为你在步骤 2 中假设的公式。
2. 将其与原始矩阵 \(\mathbf{A}\) 相乘。
3. 简化得到的四个元素。它们应该与代入 \((k+1)\) 后的目标公式一致。

快速总结框：
• 级数： 加上下一项。
• 整除性： 处理幂次并「拆解」表达式。
• 数列： 将公式代入递推关系式。
• 矩阵： 将 \(\mathbf{A}^k\) 乘以 \(\mathbf{A}\)。

最终总结：「秘密武器」

数学归纳法并不是为了求解一个方程式，而是为了搭建一座桥梁。你证明这座桥从 \(n=1\) 开始，并且证明如果桥能到达 \(k\) 点，它就一定能到达 \(k+1\) 点。如果你完成了这两件事，你就证明了这座桥可以无限延伸！

考试小撇步： 即使你在步骤 3 的代数运算中卡住了，也务必写下步骤 1 和步骤 4 的正式结论。只要了解证明结构，你就能轻松拿到不少分数！