為什麼要用猜的？
上一篇導覽交給你 遞迴樹法，你也看到把 T(n) = 2 T(n/2) + n 展開成一棵樹後，答案 Theta(n log n) 幾乎是呼之欲出。但手畫的樹是草圖，不是證書。取整被四捨五入掉、每層的總和用肉眼估計、一個漏掉的對數因子很容易溜走。代入法——又叫 猜測並驗證——就是把那張草圖變成滴水不漏之物的方法：你寫下遞迴樹所提示的答案，再用數學歸納法證明它。
這個名字對運算順序很誠實。你先猜一個封閉形式——比方說 T(n) = O(n log n)——之後才去驗證它。驗證就是一個普通的歸納法證明，而它「不留情面」的方式恰到好處：猜錯了，不會生出一個誤導人的證明，而是根本生不出證明。代數就是封不起來。這正是它全部的魅力——代入法 不會像手畫的樹那樣，被一個看似合理的總量給騙過去。
兩個步驟，逐步走一遍
讓我們從頭到尾證明 T(n) = 2 T(n/2) + n 是 O(n log n)。引擎是 對輸入規模做歸納，又因為遞迴式向下伸到規模 n/2，它自然是 強歸納法：我們可以假設此界對「每一個」比 n 小的規模都成立，而不只是對 n - 1。以下是遞迴式與我們要辯護的猜測。
Recurrence: T(n) = 2 T(n/2) + n, T(1) = 1
Guess: T(n) <= c * n * log n (for some constant c > 0, n >= 2)
Inductive step, assume it for n/2:
T(n) <= 2 * [ c * (n/2) * log(n/2) ] + n
= c * n * (log n - 1) + n
= c * n * log n - c * n + n
= c * n * log n - (c - 1) * n
<= c * n * log n whenever c >= 1- 猜一個封閉形式。遞迴樹提示 Theta(n log n)，所以為了上界，我們試 T(n) <= c n log n，常數 c 留待稍後敲定。
- 假設它對較小的規模成立。由強歸納法假設 T(n/2) <= c (n/2) log(n/2)。這是歸納假設——是我們唯一被允許倚靠的東西。
- 代入並化簡。把它放進遞迴式；利用 log(n/2) = log n - 1，右邊塌縮成 c n log n - (c - 1) n。
- 把界封起來。剩下的項 -(c - 1) n 在 c >= 1 時恰好 <= 0，所以右邊 <= c n log n——正是我們所猜的「同一個」形式。歸納成立。
- 檢查基底情況。挑一個小範圍（比如 n = 2 與 n = 3），把 c 取得夠大，使 T(n) <= c n log n 在那裡也成立。如此一來，此界對所有 n >= 2 都成立。
請注意 基底情況 不是事後補的——它是證明的一半。歸納只把界從較小的輸入往上帶，所以必須有東西錨定最底端。我們可以自由地從 n = 2 開始歸納（而非從 n = 1，因為 log 1 = 0 會使 c n log n 塌成 0 而失效），並把 c 取得夠大，蓋住那少數幾個小規模。略過這一步，是代入法證明中最常見、也最隱形的漏洞。
同一個常數，否則證不出來
這裡有一個微妙之處，幾乎每個人第一次都會中招。要用歸納法證明 T(n) <= c n log n，代入後的右邊必須封回 c n log n，且是「完全同一個」常數 c——不是 c n log n 再加一個多餘的項，也不是某個含糊的 O(n log n)。常數必須從假設原封不動地存活到結論。只要還黏著一個剩餘項，歸納就沒封起來，無論那一項看起來多小。
來看那個經典的錯誤證明。取 T(n) = 2 T(n/2) + n，猜一個錯的界 T(n) = O(n)。假設 T(n/2) <= c (n/2)。則 T(n) <= 2 c (n/2) + n = c n + n。粗心的人會說「這是 O(n)，搞定。」其實沒搞定——它是 c n + n，也就是 (c + 1) n，「不是」c n。常數變大了。再往下推一層，它變成 (c + 2) n，然後 (c + 3) n；常數每層往上爬一格，經過 log n 層後爬到約 c + log n，所以 T(n) 其實是 n log n，而不是 n。這個失敗的歸納正是在告訴你：猜得太弱了。
強化的訣竅：減去一個低階項
有時猜測是對的，但顯而易見的形式就是封不起來，而解法感覺很弔詭：你證明一個「更強」的命題，反而讓歸納成功。考慮 T(n) = 2 T(n/2) + 1、T(1) = 1；遞迴樹顯示約有 n 個葉子、各花費 1，所以答案是 O(n)。然而猜 T(n) <= c n 會失敗。假設 T(n/2) <= c (n/2)；則 T(n) <= 2 c (n/2) + 1 = c n + 1，而那個討厭的 +1 表示界 c n 沒有自我重現——正是上一節那個剩餘項的失敗。
修補的方法是猜 T(n) <= c n - d，其中 c、d 為正常數——這是一個嚴格更強的主張，因為 c n - d 比 c n 小。假設 T(n/2) <= c (n/2) - d。則 T(n) <= 2 (c n/2 - d) + 1 = c n - 2d + 1 = (c n - d) - (d - 1)，只要 d >= 1，這就 <= c n - d。界現在完美封閉。多出來的 -d 給了歸納一點餘裕，讓那個 +1 可以吃進去而不溢出，又因為 d 是常數，c n - d 仍是 O(n)——這個強化在最終答案上不花一毛錢。
「證明更多反而更容易」感覺是反過來的，但這是橫跨各種 歸納法 證明的標準手法，不是遞迴式獨有的怪癖：更強的假設在歸納步驟中遞給你一件更強的工具。鏡像的錯誤——往錯的方向強化，也就是「加上」一個低階項，如 T(n) <= c n + d——會讓假設變弱，永遠封不起來。教訓是：當遞迴式裡的加性常數在滲漏時，要「減」不要「加」。
從 O 到 Theta，以及此法無法保證之事
到目前為止證的全是上界——一個 大O 結果。那只是緊界答案的一半。要宣稱 T(n) = Theta(n log n)，你還必須證明一個相符的下界 T(n) >= c' n log n（某常數 c' > 0），那是另一個把不等號翻轉的代入法證明（你假設 T(n/2) >= c' (n/2) log(n/2)，往下推到 T(n) >= c' n log n）。唯有兩個方向都封閉，你才掙得 Theta。許多寫法只證上界，然後悄悄寫上 Theta——那是誇大，是整個主題裡最常見、看起來最誠實的錯誤。
也要誠實面對這裡「已驗證」是什麼意思。代入法的證明保證的是一個漸進的界——一個關於「大 n」的陳述。它對隱藏常數 c 隻字未提，還刻意把它留成自由的，所以它無法告訴你這個演算法在你「實際會跑」的輸入規模上是否勝過另一個。漸進式描述的是成長趨勢，而非每個規模下的判決；當 n 很小、被丟掉的常數與低階項主導時，一個 O(n log n) 的方法仍可能輸給一個 O(n^2) 的方法。代入法回答的是「成本如何成長？」，而非「在我今天的筆電上哪個比較快？」。
最後，此法觸及範圍真實，侷限也真實。它能處理下一篇 主定理 處理不了的遞迴式——不均的切割、加上對數、合併裡多一個 +log n——因為歸納法不在乎遞迴式是不是整齊的 a T(n/b) + f(n) 形狀。但它不是發現答案的工具，當正確的猜測需要巧妙的強化時它會很瑣碎，而一個讓常數漂移的草率證明能「證出」一個假的界。然而只要守住同一個常數的紀律，它就是遞迴樹與主定理底下共同的嚴謹骨幹，而最後一篇的 Akra-Bazzi 方法 也仰賴同樣的猜測並驗證精神。