強歸納法（strong induction）

普通歸納法讓你假設敘述在 n 成立，再證明它在 n+1 成立——每張骨牌恰好倚靠前一張。但有時某個情形依賴的不是緊鄰的前一個情形，而是好幾個更早的情形，或一個大約只有它一半大的情形。強歸納法把假設加寬：要證明 P(n)，你可以一次假設對所有更小的 k 都有 P(k)，而不只是 k = n-1。彷彿每張骨牌可以被它前面任意組合的骨牌撞倒。

嚴格地說，要證明「對所有 n >= n0，P(n)」，強歸納法讓你在證明 P(n) 時使用假設「對每個 n0 <= k < n，P(k) 成立」。（通常甚至不需要另寫基底情形，因為最小的 n 沒有更小的 k，假設為空，所以你必須直接把那個情形建立起來。）一個經典例子：每個整數 n >= 2 都有質因數分解。若 n 是質數，完成。若 n = a*b 且 1 < a, b < n，則由強假設，a 與 b 都已能分解為質數，故 n 也能。注意我們用到的是兩個比 n 小的數的結論，且都不一定是 n-1——這正是普通歸納法給不了我們的。

強歸納法是分治與遞迴演算法的天然工具：解規模 n 時會呼叫規模 n/2、或 n-1 與 n-2、或任意更小規模的子問題。證明這類程序正確，通常會說「假設遞迴呼叫對所有更小輸入都正確（強假設），再證明合併步驟正確」。原則上它不比普通歸納法更強——兩者可互相模擬——但當某情形倚靠許多個或相距很遠的更小情形時，它方便太多了。