目錄
這是 Stanford CS103 導讀的第 15 篇，對應 Spring 2026 官方 Lecture 13（2026-04-29）。課程團隊是 Cynthia Bailey Lee 與 Alex Aiken；公開頁面沒有逐堂標示實際講者，因此本文不猜講者。講次頁面與完整投影片公開，錄影與逐字稿只在 Canvas／Panopto，本文沒有使用。
本講的官方題目是 Mathematical Induction, Part II。CS103 的讀法不是背一排名詞，而是依序問：物件如何定義、哪些輸入合法、主張要求什麼，以及什麼論證才足以支持結論。這篇依投影片的定義與例子整理；沒有出現在公開 投影片 的口頭補充，不會被補寫成課堂內容。
從上一講的標準歸納法出發
投影片先重播上一講的核心。給定述詞 (P)，若 (P(0)) 成立，而且對每個 (k\in\mathbb N)，(P(k)\to P(k+1))，便可推出所有自然數 (n) 都滿足 (P(n))。這個原理的重點不是「檢查很多例子」，而是建立一條不會中斷的推進鏈：base case 把第一塊骨牌立起來，inductive 步 保證每一塊已倒下的骨牌都會推倒下一塊。
投影片 再次展示前 (n) 個 2 的冪次和。令
[ P(n): \sum_{i=0}^{n-1}2^i=2^n-1. ]
在 (n=0) 時，左側是空和 0，右側是 (2^0-1=0)。假設任意 (k) 滿足 (P(k))，則
[ \sum_{i=0}^{k}2^i =\left(\sum_{i=0}^{k-1}2^i\right)+2^k =(2^k-1)+2^k =2^{k+1}-1. ]
這段 recap 刻意保留三個寫作責任：先定義述詞、清楚標示哪個等號使用 inductive hypothesis、最後才由歸納原理推出全稱結論。本講接著改動的不是這套邏輯，而是「從哪裡開始」、「一次走幾步」以及「一步可以假設多少個較小案例」。
起點不必是零
若命題只聲稱對 (n\ge m) 成立，base case 就應是 (P(m))，inductive 步 也只需對任意 (k\ge m) 證明 (P(k)\to P(k+1))。結論相應縮成所有 (n\ge m) 都有 (P(n))。不能一面從 (m) 起跑，一面宣稱已覆蓋 (0,1,\ldots,m-1)；那些數根本不在推進鏈上。
例如主張從 6 開始，證 (P(6)) 後可依次抵達 7、8、9。若只證 (P(7))，就無法倒推 (P(6))。反過來，題目若只要求 (n\ge6)，硬加 (P(0)) 到 (P(5)) 不但多餘，有時甚至是假的。選起點應忠實對應定理的 domain，而不是把「從 0 開始」當格式習慣。
步長大於一時，必須照顧每條餘數鏈
inductive 步 也不必永遠是 (+1)。但若證的是 (P(k)\to P(k+3))，從一個 base case 只能覆蓋同一個 modulo 3 的數。例如從 6 只能得到 9、12、15；它永遠到不了 7 或 8。因此若目標是所有 (n\ge6)，需要三個起點 (P(6),P(7),P(8))：
- (6,9,12,\ldots) 覆蓋餘數 0；
- (7,10,13,\ldots) 覆蓋餘數 1；
- (8,11,14,\ldots) 覆蓋餘數 2。
這也是 投影片 對「多個 base cases」最精準的警告。base cases 不是越多越安全：必須足夠覆蓋每條推進鏈，也不要加入已能由其他 base 與 步 推出的冗餘案例。可執行的檢查法是把起點寫成集合 (B)，反覆加上 步 size (d)，列出前二十個可達數；目標區間若出現洞，證明就未覆蓋全域。
正方形分割問題：先辨認哪些 n 可行
投影片 的幾何問題問：一個正方形能否被分割成恰好 (n) 個較小正方形？小正方形不能重疊，也不能伸出原正方形。(n=1) 當然可行，因為整個正方形本身就是一塊；(n=2) 與 (n=3) 則不可行。
投影片用四個角解釋小數量的障礙。原正方形的每個角，都必須由某個分割後正方形的角覆蓋。若小正方形少於四個，鴿籠原理迫使至少一塊同時覆蓋原圖形的兩個角；對軸對齊且完整鋪滿的正方形而言，這會迫使那一塊跨越整個邊長，留下無法由其餘一兩塊正方形合法鋪滿的區域。投影片 接著畫出 (4,5,6,7,8,9,10,11,12) 的具體配置，讓讀者先由構造辨認模式，而不是空猜公式。
真正關鍵的 insight 是局部替換。已知某個 (n)-塊分割後，任選其中一塊，把它切成四個相等的小正方形。原本的一塊被移除，加入四塊，總數淨增加 (-1+4=3)。因此
[ P(n)\Longrightarrow P(n+3), ]
其中 (P(n)) 表示「存在把正方形分成 (n) 個較小正方形的方法」。這個述詞是存在命題；inductive 步 的責任是由假設中的一個既有分割，明確構造出新分割。
完整證明：所有 n ≥ 6 都能分割
定理是：對任意 (n\ge6)，存在把正方形分成 (n) 個較小正方形的方法。令 (P(n)) 如上。base cases 是 投影片 畫出的 6、7、8 塊合法分割。它們各自啟動一條 modulo 3 鏈，三者都不可少。
inductive 步 取任意 (k\ge6)，假設 (P(k)) 成立，也就是手上確實有一個 (k) 塊分割。挑其中任何一塊四等分；新圖形仍完全位於原正方形內，四塊互不重疊，並與其他 (k-1) 塊一起完整覆蓋原圖形。總數為
[ (k-1)+4=k+3, ]
所以 (P(k+3)) 成立。以 6、7、8 為 bases 並重複此 步，任意 (n\ge6) 都落在恰好一條餘數鏈上，定理得證。
注意這不是一般的 (+1) 歸納法。若把結論錯寫成「由 (P(k)) 得 (P(k+1))」，幾何構造只增加三塊，證明便與聲稱的 步 不符。若只列 6 為 base，也只證到 3 的倍數。這兩個錯誤都可由「真的列出接下來可達的數」立即抓到。
完全歸納法：一步可以使用所有較小案例
完全歸納法（complete induction，也常稱 strong induction）的原理是：證明 base case 後，對任意 (k)，假設 (P(0),P(1),\ldots,P(k)) 全部成立，再推出 (P(k+1))。最後仍得到每個自然數都滿足 (P)。若起點是 1，假設區間也相應改成 (P(1),\ldots,P(k))。
它與一般歸納法的差異在可用資訊，而不是結論更「強」。一般歸納 步 只有 (P(k))；完全歸納 步 可以挑任何需要的較小案例。當一個大小 (k+1) 的物件會拆成不固定大小的子物件時，只知道緊鄰的 (P(k)) 往往不夠，知道所有較小尺寸才自然。
量詞必須讀準：先「任取 (k)」，再在這個固定但任意的 (k) 下假設區間內每個命題成立。不能為了證 (P(k+1)) 使用 (P(k+1)) 自己，也不能使用更大的 (P(k+2))。完全歸納不是允許任意假設，而是允許全部嚴格較小的案例。
巧克力棒：為何需要整段 inductive hypothesis
投影片 的例子是一條 (1\times n) 巧克力棒，由左到右吃。每一口可以掰下左端一個或多個方格；不同吃法由每口大小的序列區分。小例子是 (n=1,2,3,4) 時分別有 (1,2,4,8) 種，猜想一般共有 (2^{n-1}) 種。
令 (P(n)) 表示「吃完 (1\times n) 巧克力棒恰有 (2^{n-1}) 種方法」。base case (n=1)：只能整塊一口吃掉，所以方法數為 (1=2^0)。
對 inductive 步，取任意 (k\ge1)，假設 (P(1),\ldots,P(k)) 都成立。要數 (k+1) 格的吃法，依第一口分類。若第一口直接吃掉全部，只有 1 種。否則第一口大小為某個 (r\in{1,ldots,k})，剩下 (k+1-r) 格。這個剩餘長度介於 1 與 (k)，所以能合法套用對應的 inductive hypothesis，剩餘部分有
[ 2^{(k+1-r)-1}=2^{k-r} ]
種吃法。不同第一口大小互斥且涵蓋所有情況，因此總數是
[ 1+\sum_{r=1}^{k}2^{k-r} =1+(2^{k-1}+2^{k-2}+\cdots+2^0) =1+(2^k-1) =2^k. ]
這正是 (P(k+1))。為何普通 induction hypothesis (P(k)) 不方便？第一口若吃兩格，剩下的是 (k-1) 格；吃三格，剩下 (k-2) 格。分類會同時引用許多不同的較小尺寸，完全歸納恰好提供整段假設。
另一條直接計數視角，以及它沒有取代什麼
同一答案也可由切口得到：(n) 格之間有 (n-1) 個縫，每個縫獨立選擇「這一口在此結束」或「與下一格同一口」，所以有 (2^{n-1}) 個子集合，也就有 (2^{n-1}) 種吃法。這個 bijection 是很好的答案檢查，但 投影片 使用完全歸納，是為了示範當第一步留下任意較小子問題時，如何合法使用所有較小案例。
因此不要把「找到更短的組合證明」誤成「歸納證明錯了」。同一命題可以有多種證法；本講關心的是 證明 obligation：分類是否互斥且完備、每個 remainder 是否真的落在假設範圍、幾何級數是否少算或重算。
一般歸納與完全歸納其實等價
投影片 最後比較兩者。完全歸納看似允許更多假設，但兩個原理在邏輯能力上等價。要用普通 induction 模擬完全 induction，可定義
[ Q(n): P(0)\land P(1)\land\cdots\land P(n). ]
證 (Q(k)\to Q(k+1)) 時，(Q(k)) 已打包所有較小的 (P)，先用原問題的 complete-induction 步 得到 (P(k+1))，再與既有合取合併成 (Q(k+1))。反方向更直接：若只需要 (P(k))，完整假設 (P(0),\ldots,P(k)) 當然包含它。
實務上應選讓遞迴結構最清楚的版本。子問題永遠只縮一格，就用普通 induction；會縮成任意較小尺寸，就用 complete induction；一次加三且要覆蓋全部整數，就明列三個 bases 與餘數鏈。形式要跟構造走，不是跟熟悉度走。
可執行自測：逐行審核歸納證明
拿一張紙完成以下檢查。第一，寫出 (P(n)) 的完整句子與合法 domain。第二，圈出最小目標值，確認 base case 正是那個起點。第三，把 步 寫成帶量詞的蘊含式，例如 (\forall k\ge6,(P(k)\to P(k+3)))。第四，從每個 base 手算前四個可達值，檢查是否覆蓋目標。第五，在證明中每次使用 hypothesis 時標註所用的 index，確認它小於等於 (k)。
對正方形題，自測 (n=14)：它與 8 同餘 modulo 3，從 8 經兩次四等分得到 11、14。對巧克力題，自測 (n=4)：第一口為 4 有 1 種；第一口為 1、2、3 時，剩餘方法數分別為 4、2、1，合計 8。若你的分類不是 (1+4+2+1)，就檢查是否把「整條一口」與某個 remainder case 重複計算。
材料缺口與閱讀界線
完整投影片足以辨認課程安排、定義與主要例子，因此這講通過 fidelity gate。但投影片不是錄影，不包含所有口頭轉折、學生問題或臨場補充。本文只把公開 投影片 能支持的內容歸於課程，不把作者的銜接文字包裝成講師原話。
更新紀錄
- 2026-08-22：依 clean review 重查「從上一講的標準歸納法出發」的投影片覆蓋，並修正失效連結、metadata 與中文語域。
參考資料
Loading...