數學歸納法（mathematical induction）
想像一排無窮長的骨牌。你想論證它們會全部倒下。你不會去一張張推——它們有無窮多張。你改為證明兩件事：第一張骨牌會倒，而且每一張只要倒了就會撞倒下一張。這兩點合起來，就保證了整排骨牌會一路倒到底。數學歸納法正是把這個動作變成一種證明技巧，用來處理「對每個自然數 n 都成立」的敘述：先對最小的 n 證明，再證明「在 n 為真就逼出在 n+1 為真」。
嚴格地說，要證明「對所有 n >= n0，P(n) 成立」，你要證明基底情形 P(n0)，再證明歸納步驟「對所有 n >= n0，若 P(n) 則 P(n+1)」。步驟中那個假設「P(n)」就是歸納假設。兩者都完成後，P 對 n0 成立，因而對 n0+1、對 n0+2……對每個 n 都成立——全收進一個有限的論證裡。一個小例子：要證 1 + 2 + … + n = n(n+1)/2，基底 n=1 給出 1 = 1*2/2；步驟假設公式在 n 成立，再加上 (n+1)：n(n+1)/2 + (n+1) = (n+1)(n+2)/2，正是 n+1 處的公式。對所有 n 證畢。
歸納法是演算法中大多數正確性與執行時間證明背後的引擎：迴圈不變量是對輪次的歸納，遞迴正確性是對輸入規模的歸納，而像 T(n) = 2T(n/2) + n 這類遞迴關係式則靠猜一個界再用歸納驗證來解。誠實的提醒：歸納法能證明一個敘述為真，卻不提供「為何如此」或「如何發現正確敘述」的直覺——而只要有一個缺口（漏掉基底情形，或步驟其實偷偷需要一個你沒假設的更小情形），整個論證就會悄悄失效。
主張：高度為 h 的二元樹至多有 2^(h+1) - 1 個節點。基底 h=0：單一節點，且 2^1 - 1 = 1。步驟：高度為 h+1 的樹是一個根加上兩棵高度 <= h 的子樹，故至多 1 + 2(2^(h+1) - 1) = 2^(h+2) - 1 個節點。對所有 h 成立。
基底情形 + 歸納步驟 = 對每個 n 為真，全在一個有限論證中。
千萬別略過基底情形：有正確的歸納步驟卻沒有成立的基底，等於什麼都沒證明（骨牌根本沒開始倒）。同樣地，步驟必須真的只用到它所假設的歸納假設。