目錄
這是 Stanford CS103 導讀的第 14 篇，對應 Spring 2026 官方 Lecture 12（2026-04-27）。課程團隊是 Cynthia Bailey Lee 與 Alex Aiken；公開頁面沒有逐堂標示實際講者，因此本文不猜講者。講次頁面與完整投影片公開，錄影與逐字稿只在 Canvas／Panopto，本文沒有使用。
本講的官方題目是 Mathematical Induction, Part I。投影片先用全場依序做 wave 建立直覺，再寫出歸納原理；接著用二的冪次和示範正式證明，以假幣問題呈現遞迴式演算法，最後用錯誤證明與 MU puzzle 說明 base case 和不變量為何不可省略。這些例子都在追問同一件事：一個性質如何從目前狀態可靠地傳到下一個狀態。
Wave：歸納法的兩個齒輪
想像一排人做 wave。第一個人先舉手；此後，每個人只要看到前一位舉手，就跟著舉手。如果兩件事都可靠，波浪就會一路傳到底。第一個條件給出起點，第二個條件給出傳播規則。只證明其中之一不夠：沒有人開始，規則永遠不會觸發；規則中途斷掉，也無法保證後面的人加入。
令 P(n) 表示「第 n 個位置具有某性質」。若 P(0) 為真，而且對每個 k ∈ ℕ 都有 P(k) → P(k+1)，就能推出 ∀n ∈ ℕ. P(n)。從 P(0) 與第二項的 k=0 得到 P(1)，再以 k=1 得到 P(2)，如此延續。投影片逐格畫出的箭頭不是無限次手工驗證，而是在展示由起點和統一傳播規則構成的鏈。
歸納證明的三段式
歸納原理是一個推理原則；歸納證明則是使用它的寫作格式。CS103 把格式拆成三步：
- Base case：證明
P(0)。 - Inductive step：任取
k ∈ ℕ，假設P(k)，證明P(k+1)。 - Conclusion：由數學歸納法，
P(n)對所有n ∈ ℕ成立。
第二步通常是全稱蘊涵的直接證明。k 必須任意，不能挑一個方便的數；P(k) 是 inductive hypothesis，只在證明 P(k+1) 時使用。它不是預先假定整個定理，也不是把待證結論循環地當成前提。先寫出 P(n) 的精確內容，才能看清楚每一步真正承擔什麼義務。
先定義 P(n)，再開始算
投影片第一個完整定理是：前 n 個二的冪次之和為 2^n-1。把空和納入，命題是：
P(n): 2^0 + 2^1 + ... + 2^(n-1) = 2^n - 1.這個定義同時決定 base case 與下一步目標。P(0) 說「前零項之和等於 2^0-1」，左右都是零；P(k+1) 則多出最後一項 2^k。若沒說清楚索引範圍，很容易把最後一項錯寫成 2^n，或在 base case 臨時換成從 n=1 開始。
觀察 1, 1+2, 1+2+4, ... 得到 1, 3, 7, 15, 31，可以幫忙猜公式，卻不是證明。有限多個數值吻合，只表示猜測尚未遇到反例；歸納證明才說明所有自然數輸入都被同一機制覆蓋。
完整證明：前 n 個二的冪次之和
定理。 對所有 n ∈ ℕ，前 n 個二的冪次之和是 2^n-1。
Base case。 n=0 時，前零項的和為零，而 2^0-1=0，所以 P(0) 成立。
Inductive step。 任取 k ∈ ℕ，假設
2^0 + 2^1 + ... + 2^(k-1) = 2^k - 1. (1)要證明 P(k+1)。前 k+1 項可拆成前 k 項再加新的一項：
2^0 + ... + 2^(k-1) + 2^k
= (2^0 + ... + 2^(k-1)) + 2^k
= (2^k - 1) + 2^k 由 (1)
= 2 · 2^k - 1
= 2^(k+1) - 1.所以 P(k+1) 成立。由數學歸納法，命題對所有自然數成立。證明真正的轉折是使用 (1)：歸納假設把舊的複雜區塊換成閉合公式，新的一項再把結果推到下一個索引。
形式上的量詞不能省
歸納步驟要證明的是 ∀k ∈ ℕ. (P(k) → P(k+1))。標準開頭因此是「任取 k ∈ ℕ，假設 P(k)」，終點是「所以 P(k+1)」。只寫「假設對 k 成立」卻不讓 k 任意，無法排除論證使用特例。只做代數卻沒標出哪一行使用 P(k)，則把最重要的橋藏起來。
Base case 是普通命題 P(0)，可以使用任何合法方法。歸納步驟也一樣：外層是直接證明全稱蘊涵，內部若需要，可以再分類討論、證逆否或反證。本講的二次方和只需要代數；後面的 MU puzzle 則需要分類和先備引理。
二進位整數是公式的具體旁註
投影片指出，1+2+4+...+2^31=2^32-1 解釋了 32-bit unsigned integer 的最大值。每個 bit 對應一個二的冪次；所有 bit 都是 1 時，就是前 32 個冪次的總和。這是已證公式的應用，不是歸納法的新規則。
更重要的解題方向是：看到逐步加入 2^k 的結構，可尋找把第 k 個答案更新成第 k+1 個答案的關係。歸納法適合的不是所有「含有 n」的公式，而是能辨認起點與穩定一步更新的主張。
三枚與九枚假幣
三枚外觀相同的硬幣中，恰有一枚較重。用天平比較其中兩枚：若一邊較重，它是假幣；若平衡，未上秤的第三枚是假幣。因此一次稱量就能定位。
九枚時，先分成三組，每組三枚，稱其中兩組。若失衡，假幣在較重的一組；若平衡，假幣在未稱的一組。第一次把候選從九枚縮成三枚，第二次套用剛才的程序。關鍵不是記住九枚的圖，而是每一次稱量都把問題縮成三分之一。
一枚需零次、三枚需一次、九枚需兩次，因而猜到 3^n 枚可用 n 次稱量。這裡的歸納假設不是等式，而是「存在一個在指定資源內完成任務的策略」。
假幣定理的歸納證明
令 P(n) 表示：若 3^n 枚硬幣中恰有一枚較重，能用 n 次稱量找出它。
Base case。 3^0=1。只有一枚時，不需稱量就知道它是哪一枚，所以 P(0) 成立。
Inductive step。 任取 k ∈ ℕ，假設能在 k 次內從 3^k 枚中找出較重者。現在有 3^(k+1)=3·3^k 枚。平均分成三組，每組 3^k 枚，稱其中兩組。一次後，依失衡或平衡可確定哪組含假幣。剩下的是大小為 3^k 的同型問題；由歸納假設，再用 k 次解完。總數 1+k=k+1，所以 P(k+1) 成立。由歸納法，定理對所有自然數成立。
歸納假設也可以是一個演算法
假幣證明顯示 P(k) 不一定是代數式。它可以說一個物件存在、一個遊戲可完成，或某演算法有資源上界。使用 P(k) 時，不是神奇地「得到答案」，而是取得一個已保證能處理較小實例的程序。
歸納步驟因此像遞迴演算法的正確性論證：先做一次工作，把輸入縮成合適的子問題，再呼叫處理子問題的保證。若分組後不是恰好 3^k 枚，或第一次稱量不能唯一選出含假幣的一組，歸納假設便接不上。證明必須交代子問題尺寸、前提與資源帳。
How Not to Induct：沒有 base case
投影片刻意「證明」錯誤公式：前 n 個二的冪次之和是 2^n。若假設錯誤的 P(k)，加上 2^k 後確實得到 2^(k+1)。換句話說，蘊涵 P(k) → P(k+1) 可能完全正確，但 P(0) 是錯的：空和為零，不是 2^0=1。
沒有真實起點，傳播規則只是說「如果錯誤公式某處碰巧成立，它會繼續成立」；它沒有提供任何成立的索引。檢查時要把 P(0) 原句代入，而不是只看作者有沒有寫出「base case」三個字。
MU puzzle 的四條改寫規則
最後的例子來自 Gödel, Escher, Bach 的 MU puzzle。從 MI 開始，希望透過四種操作得到 MU：
- 把
M後面的整段字串複製一次，例如MI → MII。 - 把任一段
III換成U。 - 若字串以
I結尾，在末端加上U。 - 刪掉任一段
UU。
盲目搜尋會產生許多字串，卻不容易知道只是尚未找到路徑，還是根本沒有路徑。投影片改追蹤字串中 I 的個數。起始 MI 有一個 I，不是三的倍數；目標 MU 有零個 I，是三的倍數。問題轉成：四種規則能否把「不是三的倍數」變成「是三的倍數」？
兩個模三引理
第一，若整數 r 不是三的倍數，r-3 也不是。證逆否：若 r-3=3q，則 r=3(q+1)，所以 r 是三的倍數。
第二，若 r 不是三的倍數，2r 也不是。r 除以三的餘數只能是 1 或 2。若 r=3q+1，則 2r=6q+2，餘數為二；若 r=3q+2，則 2r=6q+4=3(2q+1)+1，餘數為一。
兩個引理恰好對應會改變 I 數量的規則：複製使 r 變成 2r；III → U 使它變成 r-3。另外兩條規則只操作 U，所以數量保持 r。
對所有操作序列做歸納
令 P(n) 表示：「任意做完 n 次合法操作後，字串中的 I 數都不是三的倍數。」這裡的「任意」很重要；我們要排除所有可能解法，而非只分析某條路徑。
Base case。 零次後仍是 MI，I 數為一，所以 P(0) 成立。
Inductive step。 任取 k，假設任意 k 次後的 I 數 r 都不是三的倍數。考慮任意長度 k+1 的操作序列，查看最後一次：複製後為 2r，由第二引理仍非三的倍數；以 U 取代 III 後為 r-3，由第一引理仍非三的倍數；附加 U 或刪除 UU 則保持 r。所有合法末步都保持性質，所以 P(k+1) 成立。由歸納法，不論做幾步，I 數都不會是三的倍數。
從不變量到不可能性
假設 puzzle 有解，存在合法操作把 MI 變成 MU。終點含零個 I，零是三的倍數；但剛才已證明任何有限操作序列之後，I 數都不是三的倍數，矛盾。因此 MI 不可能變成 MU。
投影片把這種結構連到 loop invariant：若性質在執行前成立，而且每一步都保持它，任意有限步後仍成立。演算法證明常以同樣方式處理迴圈：初始化對應 base case，保持性對應 inductive step，終止時再把不變量與離開條件合併成結果。
寫歸納證明的可執行檢查表
P(n)是否是有明確量詞、索引與前提的命題？- 起始索引真是零嗎？
P(0)展開後是否成立？ - 歸納步驟是否任取
k，而不是驗證特定數？ - 是否只假設
P(k)，並明確寫出要證P(k+1)？ - 使用假設時，子問題是否完全符合其前提？
- 若有多種下一步，是否涵蓋所有合法情況？
- 最後是否明說由歸納法得到對所有自然數成立？
最實用的除錯方式，是把 base case、假設與目標各自完整展開。二次方和會露出空和與指數的 off-by-one；假幣問題會露出三組尺寸；MU puzzle 會露出「某條路徑」和「所有路徑」的量詞差異。
材料缺口與閱讀界線
完整公開投影片足以支持 wave、歸納原理、兩個完整示範、錯誤證明、MU puzzle 與 loop invariant 的連結。投影片也列出假幣問題的趣味變形，但沒有在 deck 中展開解答；本文不代替課堂補完。錄影、學生回應與口頭轉折不公開，也不被重建成講師原話。
下一講預告從較晚位置起步、一次跨較大步及 complete induction；那些變形留在系列下一篇，不提前混入本講。
更新紀錄
- 2026-08-22：從官方 Lecture 12 完整投影片重建遺失正文，恢復二的冪次和、假幣問題、錯誤歸納與 MU puzzle 的逐段證明。
參考資料
Loading...