數學歸納法

數學歸納法是證明命題 P(n) 對每個自然數 n 都成立的標準技術。其形象是一排骨牌：若你推倒第一張（基礎情形），又已安排好每張都會推倒下一張（歸納步驟），那麼它們就全部倒下。你只核驗兩件事，卻斷定無窮多件。

確切地說，要證「對所有 n ≥ n0 有 P(n)」，你需確立 (1) 基礎情形 P(n0)，以及 (2) 歸納步驟：對每個 k ≥ n0，蘊涵 P(k) ⇒ P(k+1)。步驟 (2) 中臨時採用的假設 P(k) 稱為歸納假設；你在某一階段假定命題成立，以便推出下一階段成立。由這兩個事實，原理便給出對每個 n ≥ n0 的 P(n)。

一個常見變體是強歸納法（或完全歸納法），其步驟可假定從 n0 直到 k 的所有 P(j)，而不僅僅是 P(k)；它邏輯上與普通歸納法等價，但當 P(k+1) 依賴於若干較早情形時頗為方便。歸納法不是「從例子猜測」（那是經驗性的、不可靠的）；它是一條嚴格的演繹原理，與自然數的良序性等價。一個常見錯誤是遺漏或錯述基礎情形——沒有第一張骨牌，步驟再好也無一倒下。