数学归纳法

例子

假设我们要证明下面这个公式（命题）：
其中n为任意自然数。这是用于计算前n个自然数的和的简单公式。证明这个公式成立的步骤如下。

第一步-起始步骤

第一步是验证这个公式在n = 1时成立。我们有左边= 1，而右边=，所以这个公式在n = 1时成立。第一步完成。

第二步-推递步骤

第二步我们需要证明如果假设n = m时公式成立，那么可以推导出n = m+1时公式也成立。证明步骤如下。
我们先假设n = m时公式成立。即
（等式1）
然后在等式等号两边分别加上m + 1得到
（等式2）
这就是n = m+1时的等式。我们现在需要根据等式1证明等式2成立。通过因式分解合并，等式2的右手边
也就是说
这样便证明了从P（m） 成立可以推导出P（m+1） 也成立。证明至此完成，结论：对于任意自然数n，P（n） 均成立。

数学归纳法的变体

在应用中，数学归纳法常常需要采取一些变化来适应实际的需求。下面介绍一些常见的数学归纳法变体。

递降归纳法 又名 递归归纳法

数学归纳法并不是只能应用于形如“对任意的n”这样的命题。对于形如“对任意的n=0,1,2,...,m”这样的命题，如果对一般的n比较复杂，而n=m比较容易验证，并且我们可以实现从k到k-1的递推，k=1,...,m的话，我们就能应用归纳法得到对于任意的n=0,1,2,...,m，原命题均成立。

数学归纳法的合理性

皮亚诺公理视数学归纳法不证自明，设作公设，而于ZFC集合论，数学归纳法可从良序定理（well-ordering principle）推导出来。