数学归纳法

数学归纳法是证明命题 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) 依赖于若干较早情形时颇为方便。归纳法不是“从例子猜测”（那是经验性的、不可靠的）；它是一条严格的演绎原理，与自然数的良序性等价。一个常见错误是遗漏或错述基础情形——没有第一张骨牌，步骤再好也无一倒下。