你早就做過的同一個動作
在上一篇指南中，你分三部分證明了一個迴圈不變量：它在迴圈開始前成立（初始化）、每一輪都保持為真（維持），離開時把結果交給你（終止）。如果那感覺像是同一招重複用了三次，你注意到的是真實的東西。前兩部分正是數學歸納法，只是穿上了迴圈的外衣。這篇指南把偽裝揭開，正面認識歸納法；因為一旦你看清它的本來面目，你也能把它用在遞迴上——那裡沒有迴圈邊界可以倚靠。
經典的圖像是一排無窮長的骨牌。你想讓它們全部倒下，卻無法一張張去推——它們有無窮多張。於是你證明兩件事：第一張骨牌會倒，而且每一張只要倒了就會撞倒下一張。這兩個事實合起來，就逼得整排倒下。這就是歸納法證明的全部構想：對最小的 n 證明敘述 P(n)，再證明 P(n) 為真會逼出 P(n+1) 為真，於是你就用一個有限的論證，一次證明了對每個 n 的 P(n)。
兩個義務，乾淨地陳述
要證明「對所有 n >= n0，P(n) 成立」，你恰好欠兩樣東西。基底情形：直接檢驗，把 P(n0) 證出來。歸納步驟：證明對每個 n >= n0，「若」P(n) 成立「則」P(n+1) 成立。那個「若」字很要緊——在步驟裡你被允許免費假設 P(n)；這個假設稱為歸納假設。你並不是在假設你想證明的最終結論；你只是對緊鄰的更小情形假設它，並把它當作通往下一步的踏腳石。
這裡是最小的、誠實的例子，從頭做到尾。主張：對所有 n >= 1，1 + 2 + ... + n = n(n+1)/2。基底情形 n = 1：左邊是 1，右邊是 1 乘 2 除以 2，等於 1。兩者相符，所以 P(1) 成立。歸納步驟：假設 P(n)，即 1 + 2 + ... + n 等於 n(n+1)/2。則 1 + 2 + ... + n + (n+1) 等於 n(n+1)/2 + (n+1)，把 (n+1) 提出來得到 (n+1)(n+2)/2——這正是 P(n+1)。兩個義務都履行了，所以公式對每個 n 成立。注意步驟裡做了真正的代數運算；它不是把目標重述一遍而已。
當一張骨牌不夠時：強歸納法
普通歸納法讓情形 n+1 恰好倚靠情形 n——每張骨牌被緊鄰前一張撞倒。但許多演算法並不是這樣分裂的。一個分治法在規模 n 上會遞迴到規模 n/2；有些遞迴呼叫規模 n-1 與 n-2；還有些一次呼叫好幾個更小的規模。對這些情形，倚靠「緊鄰的前一個情形」根本是錯的形狀——你需要的情形可能只有一半大，而不是小一號。
強歸納法把假設加寬以符合需要。要證明 P(n)，你可以一次假設「對每個」更小的 k 都有 P(k)——全部的 k，而不只是 k = n-1。彷彿每張骨牌可以被它前面任意組合的骨牌撞倒。一個乾淨的例子：每個 n >= 2 的整數都能分解成質數。若 n 是質數，完成。若 n = a 乘 b，且 a 與 b 都嚴格介於 1 與 n 之間，那麼由強假設，a 與 b 都已能分解成質數（兩者都比 n 小），所以把它們的分解縫合起來就分解了 n。我們用到了兩個比 n 小的情形，且都不是 n-1——這是普通歸納法絕不會交給我們的。
兩點誠實的提醒。第一，用強形式時，表面上常常不需要另寫基底情形，因為最小的 n 沒有更小的 k，假設為空，所以你仍須直接把那個最小情形建立起來——這個義務不會消失，只是藏起來了。第二，強歸納法並不比普通歸納法更強（兩者可互相模擬），它只是當某情形倚靠好幾個或相距很遠的更小情形時更方便。當遞迴不是恰好每次減一時，就動用它。
信任一個遞迴：對輸入規模的歸納
強歸納法是信任遞迴演算法的天然方式，而且這個框架極為實用：把每個遞迴呼叫當成一位你信任的同事。假設每個遞迴呼叫對它更小的輸入都回傳正確答案（這就是歸納假設），然後只需證明你把這些正確答案組裝成整體的正確答案。這就是對遞迴呼叫的歸納——對輸入規模做歸納，而遞迴呼叫扮演假設的角色。你從不一次推理整棵呼叫樹；你只檢查一層，其餘的交給歸納法掃完。
- 基底情形：非遞迴的輸入（小到可直接回答——空串列或單一元素串列）直接回傳正確答案。對合併排序而言，長度至多為 1 的串列本就已排序。
- 歸納假設：假設每個對嚴格更小輸入所做的遞迴呼叫都回傳正確結果。把每個回傳值當作單純就是正確的黑盒子。
- 歸納步驟：證明合併步驟能把那些正確的子答案轉成當前輸入的正確答案。對合併排序而言，把兩個已排序的半邊合併會得到一個已排序的整體。
- 檢查輸入真的有變小：每個遞迴呼叫都必須針對嚴格更小的輸入，這樣假設鏈才會在基底情形見底，而不是永遠繞圈。
把它套到合併排序上，證明就是兩行。基底：長度至多為 1 即已排序。步驟：由假設，兩個遞迴呼叫正確地排好左半與右半；合併程序正確地把兩個已排序序列交織成一個已排序序列；因此結果已排序。因為每一半都嚴格小於整體，假設一路下降到基底情形，論證便健全。這就是完整的正確性證明——之所以短，是因為歸納法替你扛起了無窮的那一部分。
縮小不是可有可無的。若某個遞迴呼叫的輸入並非嚴格更小（比方說對相同規模遞迴），歸納就會變成循環論證，而程序也可能永不停機。同一個嚴格遞減的規模也是一個良基度量——所以這個單一事實身兼兩職，既讓假設成立，又證明了終止，那正是下一篇指南的主題。
更多風味，與誠實的附帶細則
並非只有數字才有「一個最小的，加上由更小者建出的更大者」這種樣貌。一棵樹是一個節點裝著更小的子樹；一個串列是一個頭加上更小的尾；一個算術運算式是一個數字，或兩個更小的運算式由運算子連起來。結構歸納法正是對這些東西推理：對基底形狀證明性質，再證明每條建構規則都保住它。它其實是對結構大小做的強歸納法，所以它健全的理由完全相同——各部分總是嚴格更小，於是遞迴會見底。每當遞迴恰好對應其資料的形狀時，它就是最乾淨的框架。
歸納法也運行在你早先學過的執行時間分析底下，而不只是正確性。要用代入法解像 T(n) = 2 T(n/2) + O(n) 這樣的遞迴關係式，你先猜一個界——這裡是 T(n) = O(n log n)——再用歸納法驗證它：對所有更小的輸入假設這個界，代回遞迴式，檢查代數對 n 收得起來。這個界不是憑空冒出來的；是歸納法替這個猜測背書。即使是主定理——它讓你對常見的分治遞迴跳過這項工作——也是用對遞迴層數的歸納證出來的。
T(n) = 2 T(n/2) + O(n) guess: T(n) <= c * n log n verify: assume T(n/2) <= c*(n/2)*log(n/2), substitute, show T(n) <= c*n*log n
兩段誠實的附帶細則。第一，歸納法證明一個敘述為真，卻不提供「為何它為真」或「如何發現該證明哪個正確敘述」的直覺——那個創造性的跳躍（對的不變量、對的界）得靠你；歸納法只負責稽核它。第二，只要有一個缺口，整個論證就悄悄失效：漏掉基底情形、結構歸納法證明忘了某個建構子（最常見的是空樹或空串列）、或步驟其實偷偷需要一個你從未假設的更小情形。漏看一個情形的證明，不是稍微弱一點的證明——它根本不是證明。正是這份謹慎，把真正的論證和看似合理的論證區分開來，而那正是整個這一階所建立的主題。