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 的正式結論。只要了解證明結構，你就能輕鬆拿到不少分數！