第五章：歸納法 — 動畫敘事
第六集 · Ch.5 數學歸納法
骨牌效應
想像一排骨牌：
如果第一張倒下，而且每張倒下後必定會推倒下一張，
那麼所有骨牌都會倒下。
數學歸納法，就是這個直覺的嚴格版。
如果第一張倒下，而且每張倒下後必定會推倒下一張，
那麼所有骨牌都會倒下。
數學歸納法，就是這個直覺的嚴格版。
歸納法兩個步驟
要證明「P(n) 對所有非負整數成立」，只需要兩步：
基
基底步驟（Base Case）
直接驗證
這是「推倒第一張骨牌」。
直接驗證
P(0)（或 P(1)）成立。這是「推倒第一張骨牌」。
設
歸納假設（Inductive Hypothesis）
假設
這是「假設第 k 張骨牌倒下了」。
假設
P(k) 對某個 k ≥ 0 成立。這是「假設第 k 張骨牌倒下了」。
推
歸納步驟（Inductive Step）
利用 P(k) 成立，推導出
這是「證明第 k 張倒下一定帶動第 k+1 張」。
利用 P(k) 成立，推導出
P(k+1) 也成立。這是「證明第 k 張倒下一定帶動第 k+1 張」。
✓
結論
由數學歸納法，
由數學歸納法，
P(n) 對所有 n ≥ 0 成立。
經典例題：1 + 2 + … + n = n(n+1)/2
高斯十歲就發現這個公式。用歸納法嚴格證明它：
基
Base Case (n=0)：左邊 = 0，右邊 =
0×1/2 = 0。✓設
歸納假設：假設
1+2+…+k = k(k+1)/2 成立。推
歸納步驟：需要證明
左邊 =
=
=
=
1+2+…+(k+1) = (k+1)(k+2)/2左邊 =
(1+2+…+k) + (k+1)=
k(k+1)/2 + (k+1) ← 代入歸納假設=
(k+1)(k/2 + 1)=
(k+1)(k+2)/2 ✓
✓
由歸納法，
1+2+…+n = n(n+1)/2 對所有 n ≥ 0 成立。互動：視覺化 1+2+…+n
4
橘色格子是「配對」後的樣子：把 1 和 n 配、2 和 n-1 配…
每對加起來都是 n+1，共 n/2 對，所以總和是 n(n+1)/2。
每對加起來都是 n+1，共 n/2 對，所以總和是 n(n+1)/2。
強歸納法 vs 普通歸納法
有時候，假設「k 成立」不夠用——需要假設「0 到 k 都成立」才能推出 k+1。
普通歸納法
歸納假設：P(k) 成立
只用到「前一步」，適合直接的累積問題。
例：1+2+…+n 的求和公式
強歸納法（Strong Induction）
歸納假設：P(0), P(1), …, P(k) 全部成立
可以用到「前面所有步」，適合分解型問題。
例：質因數分解定理
強歸納法和普通歸納法威力完全相同，只是假設更寬鬆，有時用起來更方便。
觀念測驗
用歸納法證明某個命題時，如果基底步驟從 n=1 開始，那麼結論是：
小結
1 / 7
本頁為動畫敘事版。看完後可前往
完整第五章
進行互動練習（歸納步驟逐行展開、視覺化方塊）。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)