證明

欢迎来到证明章节：构建数学确定性！

你好，未来的数学家！本章聚焦于证明 (Proof)，这可能是进阶纯数学 1 (FP1) 中最基础的部分。虽然其他主题教你如何计算，但本章教你如何证明你的计算和公式在任何情况下都恒成立。这不仅仅是知道答案，而是要理解为什么这个答案在每一种情况下都成立。

如果听到“证明”这个词让你感到畏惧，请不必担心。我们将几乎专门聚焦于一种强大而优雅的技术：数学归纳法 (Mathematical Induction)。学完这些笔记后，你将能够自信地处理复杂的数列、整除性问题，甚至是矩阵方程！

为什么证明在 FP1 中如此重要？

在 FP1 中，数学归纳法被用于：

- 验证数列求和公式（例如，求前 \(n\) 个平方数之和）。

- 展示某个代数表达式总是能被特定的数字整除。

- 证明涉及矩阵幂的公式（例如，计算 \(A^n\)）。

第 1 节：核心概念——数学归纳法

数学归纳法是一种用于证明命题 \(P(n)\) 对所有从某个基准值（通常为 \(n=1\)）开始的正整数 \(n\) 都成立的方法。

多米诺骨牌类比

想象你有一排无限长的多米诺骨牌。为了证明它们全部会倒下，你只需要证明两件事：

1. 第一块倒下（基础步骤 / Base Case）： 你推倒第一块多米诺骨牌（初始步骤）。

2. 连锁反应有效（归纳步骤 / Inductive Step）： 你证明如果任意一块多米诺骨牌 (\(k\)) 倒下，那么它的下一块 (\(k+1\)) 也一定会倒下。

如果你证明了这两点，你就不需要亲自推倒每一块骨牌——你已经确信它们最终都会倒下！

关键术语速查

- 假设 \(P(n)\)： 你试图证明的命题。
- 基础步骤 (Base Case)： 测试 \(P(n)\) 对于 \(n\) 的最小有效值是否成立，通常是 \(n=1\)。
- 归纳假设 (Inductive Hypothesis)： 假设 \(P(k)\) 对于某个任意整数 \(k \geq 1\) 成立。
- 归纳步骤 (Inductive Step)： 使用归纳假设 \(P(k)\) 来证明 \(P(k+1)\) 必定成立。

---

第 2 节：归纳法的三个关键步骤

每一个归纳法证明都必须按顺序遵循这三个步骤。漏掉任何一步都意味着证明无效！

第 1 步：基础步骤（展示 \(P(1)\) 成立）

这是最简单的一步。你使用最小的有效整数测试命题 \(P(n)\)。通常是 \(n=1\)，但有时题目会指定 \(n=2\) 或 \(n=0\)。

例子：如果证明数列求和公式，你需要计算 \(n=1\) 时的公式值，并展示它等于该数列的第一项。

目标： 展示当 \(n=1\) 时，左式 (LHS) 等于右式 (RHS)。

第 2 步：归纳假设（假设 \(P(k)\) 成立）

这是你做出关键假设的地方。你假设命题对于某个任意整数 \(k\) 成立。

你必须明确写出：

“假设 \(P(k)\) 对于某个正整数 \(k\) 成立。”

这为你提供了一个方程或命题，你可以在第 3 步中使用它。

类比：你假设第 \(k\) 块多米诺骨牌倒下了。

第 3 步：归纳步骤（证明 \(P(k+1)\) 成立）

这是最难也是最重要的一步，所有的代数运算都在这里发生。你必须证明如果命题对 \(k\) 成立（你第 2 步的假设），它一定也对 \(k+1\) 成立。

目标： 对 \(P(k+1)\) 的表达式进行变换，直到你可以带入或代换你假设的表达式 \(P(k)\)。

类比：你证明了第 \(k\) 块骨牌的倒下总是会导致第 \((k+1)\) 块骨牌倒下。

变换成功后，你必须写出最终的结论陈述：

“因为 \(P(1)\) 成立，且 \(P(k)\) 成立可推导出 \(P(k+1)\) 成立，根据数学归纳法原理，\(P(n)\) 对所有正整数 \(n\) 均成立。”

---

第 3 节：将归纳法应用于数列求和

归纳法在 FP1 中的一个常见用途是证明数列求和公式，通常写作求和符号 \(\sum_{r=1}^{n} f(r)\)。

假设： \(P(n): \sum_{r=1}^{n} f(r) = \text{Formula}(n)\)

让我们用一个简单的例子。假设我们要证明：
\[P(n): \sum_{r=1}^{n} r(r+1) = \frac{1}{3}n(n+1)(n+2)\]

分步示例（求和）

第 1 步：基础步骤 (\(n=1\))

LHS（前 1 项之和）： \(r(r+1) = 1(1+1) = 2\)
RHS（当 \(n=1\) 时的公式）： \(\frac{1}{3}(1)(1+1)(1+2) = \frac{1}{3}(1)(2)(3) = 2\)
因为 LHS = RHS，所以 \(P(1)\) 成立。

第 2 步：归纳假设 (\(P(k)\))

假设 \(P(k)\) 对于某个正整数 \(k\) 成立：
\[\sum_{r=1}^{k} r(r+1) = \frac{1}{3}k(k+1)(k+2)\]

我们称此为方程 (*)。

第 3 步：归纳步骤（证明 \(P(k+1)\)）

我们需要证明：
\[\sum_{r=1}^{k+1} r(r+1) = \frac{1}{3}(k+1)((k+1)+1)((k+1)+2)\] \[\sum_{r=1}^{k+1} r(r+1) = \frac{1}{3}(k+1)(k+2)(k+3)\]

从 \(P(k+1)\) 的左式开始：

\[\sum_{r=1}^{k+1} r(r+1) = \left( \sum_{r=1}^{k} r(r+1) \right) + \text{第 } (k+1) \text{ 项}\]

第 \((k+1)\) 项是通过将 \(r=k+1\) 代入 \(r(r+1)\) 得到的，即 \((k+1)(k+2)\)。

\[\text{LHS} = \sum_{r=1}^{k} r(r+1) + (k+1)(k+2)\]

现在，使用归纳假设（方程 (*)）代入前 \(k\) 项之和：

\[\text{LHS} = \frac{1}{3}k(k+1)(k+2) + (k+1)(k+2)\]

*求和问题的关键提示：提取公因式，而不是展开所有项！*

注意公因式：\((k+1)\) 和 \((k+2)\)。提取它们：

\[\text{LHS} = (k+1)(k+2) \left[ \frac{1}{3}k + 1 \right] \]

现在简化中括号里的内容：

\[\text{LHS} = (k+1)(k+2) \left[ \frac{k+3}{3} \right] \] \[\text{LHS} = \frac{1}{3}(k+1)(k+2)(k+3) \]

这与 \(P(k+1)\) 所需的右式一致。

结论： 因为 \(P(1)\) 成立，且 \(P(k)\) 可推导出 \(P(k+1)\)，根据数学归纳法原理，该公式对所有正整数 \(n\) 均成立。

❌ 求和中的常见错误

学生经常忘记加上第 \((k+1)\) 项。记住：到 \(k+1\) 的和 = 到 \(k\) 的和 加上 额外的一项！

---

第 4 节：将归纳法应用于整除性

这里的目标是证明表达式 \(f(n)\) 总是能被特定的整数 \(D\) 整除。

核心概念： 如果一个数能被 \(D\) 整除，它可以写成 \(D \times M\) 的形式，其中 \(M\) 是一个整数。

假设： \(P(n): f(n)\) 能被 \(D\) 整除。

分步示例（整除性）

证明 \(P(n): 4^n - 1\) 对于所有整数 \(n \geq 1\) 都能被 3 整除。

第 1 步：基础步骤 (\(n=1\))

当 \(n=1\) 时，\(4^1 - 1 = 3\)。因为 3 能被 3 整除，所以 \(P(1)\) 成立。

第 2 步：归纳假设 (\(P(k)\))

假设 \(P(k)\) 对于某个正整数 \(k\) 成立。即 \(4^k - 1\) 能被 3 整除。
我们可以写成： \[4^k - 1 = 3M \quad \text{(其中 } M \text{ 为整数)}\]

这是方程 (*)。关键的一点是，我们可以重写它以将 \(4^k\) 设为主项： \[4^k = 3M + 1\]

第 3 步：归纳步骤（证明 \(P(k+1)\)）

我们需要展示 \(4^{k+1} - 1\) 能被 3 整除。

首先利用指数律写出 \(P(k+1)\)：

\[f(k+1) = 4^{k+1} - 1 = 4^1 \cdot 4^k - 1\]

现在，代入方程 (*) 中 \(4^k\) 的表达式：

\[f(k+1) = 4(3M + 1) - 1\] \[f(k+1) = 12M + 4 - 1\] \[f(k+1) = 12M + 3\]

最后一步是提取除数（即 3）：

\[f(k+1) = 3(4M + 1)\]

因为 \(M\) 是整数，所以 \(4M + 1\) 也是整数。因此，\(4^{k+1} - 1\) 是 3 的倍数，即能被 3 整除。

结论： 因为 \(P(1)\) 成立，且 \(P(k)\) 可推导出 \(P(k+1)\)，根据数学归纳法原理，\(4^n - 1\) 对于所有整数 \(n \geq 1\) 均能被 3 整除。

两种主要的整除性证明策略

从 \(f(k)\) 到 \(f(k+1)\) 时，你通常使用以下两种策略之一：

策略 A：代入法（如上所示）
1. 假设 \(f(k) = D \cdot M\)。
2. 变形以孤立指数项（例如，\(4^k = 3M + 1\)）。
3. 将此项代入展开后的 \(f(k+1)\) 表达式中。
此策略非常适合类似 \(a^n - b^n\) 的简单表达式。

策略 B：减法/加法（“凑项”法）
1. 假设 \(f(k)\) 能被 \(D\) 整除。
2. 写出 \(f(k+1)\)，通过策略性地加减 \(f(k)\) 的倍数，使得剩余部分也明显是 \(D\) 的倍数。

替代整除性示例：证明 \(P(n): 8^n - 1\) 能被 7 整除。

1. \(n=1\): \(8^1 - 1 = 7\)。能被 7 整除。\(P(1)\) 成立。

2. 假设 \(P(k): 8^k - 1 = 7M\)。即 \(8^k = 7M + 1\)。

3. 证明 \(P(k+1): 8^{k+1} - 1\)。 \[8^{k+1} - 1 = 8 \cdot 8^k - 1\] 代入 \(8^k = 7M + 1\): \[8(7M + 1) - 1 = 56M + 8 - 1\] \[= 56M + 7\] 提取除数 7: \[= 7(8M + 1)\] 因为 \(8M + 1\) 是整数，所以 \(P(k+1)\) 能被 7 整除。

整除性证明的关键： 始终重写你的假设 \(P(k)\) 以孤立指数项，然后将其代入 \(P(k+1)\)。这种方法几乎总能正确地化简。

---

第 5 节：将归纳法应用于矩阵幂

在 FP1 中，归纳法用于证明矩阵 \(A\) 的 \(n\) 次幂公式是否正确。

假设： \(P(n): A^n = \text{Formula}(n)\)

分步示例（矩阵）

设矩阵 \(A = \begin{pmatrix} 1 & 0 \\ 3 & 4 \end{pmatrix}\)。证明 \(P(n): A^n = \begin{pmatrix} 1 & 0 \\ 4^n - 1 & 4^n \end{pmatrix}\) 对所有整数 \(n \geq 1\) 成立。

第 1 步：基础步骤 (\(n=1\))

LHS: \(A^1 = \begin{pmatrix} 1 & 0 \\ 3 & 4 \end{pmatrix}\)
RHS: \(\begin{pmatrix} 1 & 0 \\ 4^1 - 1 & 4^1 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 3 & 4 \end{pmatrix}\)
因为 LHS = RHS，所以 \(P(1)\) 成立。

第 2 步：归纳假设 (\(P(k)\))

假设 \(P(k)\) 对于某个正整数 \(k\) 成立：
\[A^k = \begin{pmatrix} 1 & 0 \\ 4^k - 1 & 4^k \end{pmatrix}\]

这是方程 (*)。

第 3 步：归纳步骤（证明 \(P(k+1)\)）

我们需要证明 \(A^{k+1} = \begin{pmatrix} 1 & 0 \\ 4^{k+1} - 1 & 4^{k+1} \end{pmatrix}\)。

我们知道 \(A^{k+1} = A^k A\)。

\[A^{k+1} = \begin{pmatrix} 1 & 0 \\ 4^k - 1 & 4^k \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 3 & 4 \end{pmatrix}\]

进行矩阵乘法（行乘以列）：

元素 (1, 1): \((1)(1) + (0)(3) = 1\)

元素 (1, 2): \((1)(0) + (0)(4) = 0\)

元素 (2, 1): \((4^k - 1)(1) + (4^k)(3) = 4^k - 1 + 3 \cdot 4^k\)

元素 (2, 2): \((4^k - 1)(0) + (4^k)(4) = 4 \cdot 4^k = 4^{k+1}\)

让我们简化元素 (2, 1):

\[4^k - 1 + 3 \cdot 4^k = 4^k + 3 \cdot 4^k - 1\] \[= 1 \cdot 4^k + 3 \cdot 4^k - 1\] \[= (1 + 3) \cdot 4^k - 1\] \[= 4 \cdot 4^k - 1\] \[= 4^{k+1} - 1\]

因此，\(A^{k+1} = \begin{pmatrix} 1 & 0 \\ 4^{k+1} - 1 & 4^{k+1} \end{pmatrix}\)。

这与 \(P(k+1)\) 所需的右式完全一致。

结论： 因为 \(P(1)\) 成立，且 \(P(k)\) 可推导出 \(P(k+1)\)，根据数学归纳法原理，该公式对所有正整数 \(n\) 均成立。

❌ 矩阵中的常见错误

在进行乘法时，确保你计算的是 \(A^k A\) 而不是 \(A A^k\)，除非该矩阵是可交换的（这种情况很少见！）。在矩阵乘法中，顺序非常重要！

---

最终收获：你的归纳法检查清单