数学归纳法是一种数学证明方法，用于证明关于所有自然数或从某个指定起始值开始的所有整数的命题。它既要证明初始情形成立，也要证明每一种情形成立都能推出下一种情形成立。这样，一个有限的论证就能确立无穷多个情形。尽管名称中有“归纳”二字，数学归纳法实际上是演绎推理，而不是基于观察实例的归纳推理：只要完成这两项证明，其结论就必然成立。(cs.cornell.edu)
归纳原理
设 (P(n)) 是一个依赖于整数 (n) 的命题，(n_0) 是起始值。归纳证明包含两个必不可少的部分：
- **归纳基础：**证明 (P(n_0)) 成立。
- **归纳步骤：**对于任意整数 (k\geq n_0)，假设 (P(k)) 成立，并证明 (P(k+1)) 成立。
临时作出的假设 (P(k)) 称为归纳假设。这两部分共同确立了
[ P(n)\quad\text{对每个整数 }n\geq n_0\text{ 都成立。} ]
根据命题的具体内容，起始值可以是零、一或其他整数。归纳步骤必须适用于每一个符合条件的 (k)，而不能只适用于选定的几个例子。(cs.cornell.edu)
这种证明并没有循环地假设所要证明的定理已经普遍成立。归纳步骤确立的是一个条件蕴涵关系。归纳基础给出了这一蕴涵关系的第一个前提，随后反复应用它，便能确立之后的每一种情形。在逻辑学中，在条件论证中假设 (P(k)) 成立，与直接断言 (\forall n,P(n))，有着根本的区别。(cs.cornell.edu)
证明示例
算术中的一个初等恒等式是
[ 1+2+\cdots+n=\frac{n(n+1)}2 \qquad(n\geq1). ]
将 (P(n)) 定义为这个方程。当 (n=1) 时，等号两边都等于一，因此归纳基础成立。在归纳步骤中，假设
[ 1+2+\cdots+k=\frac{k(k+1)}2. ]
两边加上 (k+1)，再运用代数运算，得到
[ \begin{aligned} 1+2+\cdots+k+(k+1) &=\frac{k(k+1)}2+(k+1)\ &=\frac{(k+1)(k+2)}2. \end{aligned} ]
这恰好就是 (P(k+1))，因此由数学归纳法可知，该恒等式对每个正整数都成立。在将前 (k) 项替换为假设中给出的和时，就用到了归纳假设。(cs.cornell.edu)
强归纳法
强归纳法也称完全归纳法，允许在归纳步骤中假设此前的所有情形都成立，而不只是紧邻的前一种情形。确立 (P(n_0)) 后，需要在以下假设下证明 (P(k+1))：
[ P(n_0),P(n_0+1),\ldots,P(k). ]
普通归纳法与强归纳法在证明能力上是等价的。要由普通归纳法得到强归纳法，只需对“从 (n_0) 到 (n) 的所有情形都成立”这一命题应用普通归纳法。更强的归纳假设往往能使证明更容易组织。(cs.cornell.edu)
例如，每个整数 (n\geq12) 都可以表示为 (4a+5b)，其中 (a,b) 为非负整数。初始情形是 (12,13,14,15)。对于任意 (n\geq16)，较小的数 (n-4) 已有这样的表示；再加上四，就得到了 (n) 的表示。这个例子也说明了为什么有些证明需要多个初始情形：归纳步骤在每个边界处都必须有一个已经确立的较早情形可供使用。(cs.cornell.edu)
理论基础与良序性
归纳原理是自然数算术的皮亚诺公理的一部分。在一阶逻辑中，它以公理模式的形式出现：每个符合条件的公式都给出一条归纳公理。以零为初始数，用 (S(n)) 表示 (n) 的后继数，这一模式的形式为
[ \bigl(P(0)\land\forall n(P(n)\rightarrow P(S(n)))\bigr) \rightarrow\forall n,P(n). ]
因此，归纳原理是一条奠定理论基础的原理，而不只是检验实例的捷径。(web.mit.edu)
在通常的经典逻辑框架下，归纳原理与自然数的良序原理等价：每个非空的自然数子集都有最小元素。如果一个归纳论证存在反例，就选取其中最小的一个。它不可能是初始情形，因此它的前一个数满足该命题，而归纳步骤又必然推出这个反例也满足该命题。这种反证法说明了归纳原理的最小反例表述。(people.math.sc.edu)
结构归纳法与计算
结构归纳法将这一方法推广到通过归纳方式生成的对象，包括有限列表、树和表达式。证明时，先证明基本对象具有所需性质，再证明只要各组成对象具有该性质，每条构造规则都能保持这一性质。普通归纳法就是其中一种特例：对象从零开始，通过反复应用后继运算生成。(cs.cornell.edu)
在计算机科学中，归纳法与递归密切相关。递归算法将任务化为规模更小的实例；归纳证明则通过假设这些较小规模的计算按规定运行，来确立算法的正确性。结构归纳法同样沿着数据结构的构造方式展开。当运行时间的递推关系涉及多个较小的输入规模时，强归纳法也有助于证明计算复杂性的界。(cs.cornell.edu)
常见错误
检验许多情形不能代替归纳步骤。反过来，只证明归纳步骤而不确立初始情形，也只能得到一条没有起点的条件推导链。有效的论证还必须涵盖其所声明范围内所需的最初一次递推。(cs.cornell.edu)
“所有马的颜色都相同”这一著名的错误证明，就展示了这种边界错误。它从一组 (k+1) 匹马中取出两组各有 (k) 匹的马，并利用两组中共有的马来推断它们的颜色相同。然而，当 (k=1) 时，这两组没有共有的马。因此，归纳步骤恰好在必须从一匹马的情形推出两匹马的情形时失效。(ocw.mit.edu)