Proof by induction

數學歸納法：征服無限步驟

你好！歡迎來到進階數學（Further Mathematics）中最優雅且至關重要的方法之一：數學歸納法（Proof by Induction）。只要能掌握這個技巧，你就能證明對無數個正整數成立的命題——這是一項極具威力的技能！

如果一開始覺得有點棘手，請別擔心。數學歸納法遵循一個固定的邏輯結構。我們其實是在學習一套構建有力論證的「數學公式」。讀完這些筆記後，你將能夠把此方法應用於求和、數列、整除性問題，甚至是複數運算！

什麼是數學歸納法？（骨牌類比）

數學歸納法是一種用於證明命題 \(P(n)\) 對所有大於或等於某個起始整數（通常是 \(n=1\)）的整數 \(n\) 均成立的方法。

骨牌效應類比

想像你有一排無限延伸的骨牌，編號分別為 1, 2, 3，依此類推。要證明所有骨牌都會倒下，你只需要證明兩件事：

1. 基本情況（第一推）： 你推倒了第一塊骨牌（第 1 塊）。
2. 歸納步驟（連鎖反應）： 你證明如果任何一塊骨牌（第 \(k\) 塊）倒下，那麼下一塊骨牌（第 \(k+1\) 塊）也一定會倒下。

如果這兩點都成立，整排無限多的骨牌就一定會全部倒下！

數學歸納法的三個必要步驟

每一個歸納法證明都必須嚴格遵守這三個步驟。請確保在考試答案中清楚地標註它們！

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

我們必須證明命題 \(P(n)\) 對最小的可能整數成立，通常是 \(n=1\)（根據題目要求，有時也可能是 \(n=0\) 或 \(n=2\)）。

• 將起始值（例如 \(n=1\)）代入命題的左式 (LHS)。
• 將起始值代入命題的右式 (RHS)。
• 得出結論：由於 LHS = RHS，因此 \(P(1)\) 成立。

步驟 2：歸納假設 (Inductive Assumption, \(n=k\))

這是我們在骨牌鏈中建立假設性連接的地方。

• 我們假設命題 \(P(k)\) 對某個任意正整數 \(k\) 成立。
• 關鍵點：請務必清楚寫出命題 \(P(k)\) 的表達式。 你將會在步驟 3 使用這個等式。

常見錯誤提醒： 學生有時會試圖證明 \(P(k)\) 是成立的，但你必須只是假設它成立。證明過程在下一步才會出現！

步驟 3：歸納步驟 (Inductive Step, \(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\) 的倍數。

範例：證明 \( 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)\) 成立。

結論： 根據歸納法，\( 7^n - 4^n \) 對所有 \(n \ge 1\) 均能被 3 整除。

應用類型 3：代數與複數證明

歸納法可用於證明一般的代數結果，包括涉及複數的結果。此單元中最著名的例子是證明迪莫弗定理（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)」的總結句。