證明

歡迎來到證明章節：建立數學確信度！

你好，未來的數學家！本章重點介紹證明（Proof），這或許是進階純數 1 (FP1) 中最基礎的部分。雖然其他課題教你如何計算，但本章教你如何證明你的計算和公式是恆真的。重點在於不僅僅是知道答案，而是要明白為什麼答案在每一種情況下都成立。

如果「證明」聽起來很嚇人，不用擔心。我們將幾乎專注於一種強大而優雅的技巧：數學歸納法（Mathematical Induction）。讀完這些筆記後，你將能充滿信心地處理複雜的數列、整除性問題，甚至矩陣方程式！

為什麼證明在 FP1 中很重要？

在 FP1 中，數學歸納法用於：

- 驗證級數和的公式（例如：求前 \(n\) 個平方數的和）。

- 證明代數表達式總能被某個特定數整除。

- 證明涉及矩陣冪的公式（例如：計算 \(A^n\)）。

第 1 節：核心概念 —— 數學歸納法

數學歸納法是一種用於證明命題 \(P(n)\) 對所有正整數 \(n\) 均成立的方法，從一個特定的基值（通常是 \(n=1\)）開始。

骨牌類比

想像你有一排無窮無盡的骨牌。要證明所有骨牌都會倒下，你只需要證明兩件事：

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\) 成立。

你必須明確寫出來：

「假設對於某個正整數 \(k\)，\(P(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{公式}(n)\)

讓我們用一個簡單的例子。假設我們要證明：
\[P(n): \sum_{r=1}^{n} r(r+1) = \frac{1}{3}n(n+1)(n+2)\]

逐步示範（級數和）

步驟 1：基本情況 (\(n=1\))

LHS（第一項的和）： \(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)\))

假設對於某個正整數 \(k\)，\(P(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)\) 的 LHS 開始：

\[\sum_{r=1}^{k+1} r(r+1) = \left( \sum_{r=1}^{k} r(r+1) \right) + (k+1)^{\text{th}} \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)\) 所需的 RHS 相符。

結論：由於 \(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)\))

假設對於某個正整數 \(k\)，\(P(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\) 的顯然倍數。

---

第 5 節：將歸納法應用於矩陣冪

在 FP1 中，歸納法用於證明矩陣 \(A\) 的 \(n\) 次冪公式是正確的。

假設： \(P(n): A^n = \text{公式}(n)\)

逐步示範（矩陣）

令矩陣 \(A = \begin{pmatrix} 1 & 0 \\ 3 & 4 \end{pmatrix}\)。證明對於整數 \(n \geq 1\)，\(P(n): A^n = \begin{pmatrix} 1 & 0 \\ 4^n - 1 & 4^n \end{pmatrix}\)。

步驟 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)\))

假設對於某個正整數 \(k\)，\(P(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 + 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)\) 所需的 RHS 相符。

結論：由於 \(P(1)\) 成立，且 \(P(k)\) 蘊含 \(P(k+1)\)，根據數學歸納法原理，該公式對所有正整數 \(n\) 均成立。

❌ 矩陣的常見錯誤

進行乘法時，務必確保計算的是 \(A^k A\) 而非 \(A A^k\)，除非矩陣是可以交換的（這很罕見！）。在矩陣乘法中，順序非常重要！

---

最終回顧：歸納法檢核清單