猜測並用歸納法驗證（guess and verify by induction）

當你遇到一個無法立刻認出的遞迴式時，可行的策略是：對它的成長率做一個有根據的猜測，再嚴謹地為這個猜測辯護。這正是代入法的核心，可看成兩種獨立的技能：猜測這一步的創造性跳躍，以及用歸納法做的紀律性檢驗。

用歸納法驗證，意思是把「T(n) 至多（或至少）等於某個公式 g(n)」當成對每個 n 都要證明的命題。歸納假設是：此界對所有較小的輸入都成立（這是強歸納法，因為遞迴式可能參照好幾個較小規模）。你把假設代入遞迴式的右邊，證明同一個界 g(n) 重新浮現，並另外驗證小 n 的基底情況。好的猜測從哪來？三個誠實的來源：能提示總量的遞迴樹；對照主定理三種情況做模式比對；或嘗試錯誤猜測的鄰居——若 T(n) <= c n 太弱，試 c n log n；若超過頭，試減去一個低階項。

把「猜」和「驗」分開的價值在於：它阻止你在沒有證明的情況下，就相信一個看起來合理的總量。遞迴樹給出很強的提示，但非正式地把各層加起來，可能漏掉一個對數因子或邊界效應；歸納法就是抓住它的安全網。反過來說，若驗證失敗，失敗通常會告訴你如何修正猜測——太弱、太強，或差一個低階項——使這成為一個有產出的循環，而非死胡同。