定义

最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步：

骨牌一个接一个倒下，就如同一个值到下一个值的过程。

证明当n = 1时命题成立。

证明如果在n = m时命题成立，那么可以推导出在n = m+1时命题也成立。（m代表任意自然数）

这种方法的原理在于：首先证明在某个起点值时命题成立，然后证明从一个值到下一个值的过程有效。当这两点都已经证明，那么任意值都可以通过反复使用这个方法推导出来。把这个方法想成多米诺效应也许更容易理解一些。例如：你有一列很长的直立着的多米诺骨牌，如果你可以：

证明第一张骨牌会倒。

证明只要任意一张骨牌倒了，那么与其相邻的下一张骨牌也会倒。

那么便可以下结论：所有的骨牌都会倒下。

例子

假设我们要证明下面这个公式（命题）：

1+2+3+⋯ ⋯ -->+n=n(n+1)2{\displaystyle 1+2+3+\cdots +n={\frac {n(n+1)}{2}}}

其中n为任意自然数。这是用于计算前n个自然数的和的简单公式。证明这个公式成立的步骤如下。

证明

第一步-起始步骤

第一步是验证这个公式在n = 1时成立。我们有左边 = 1，而右边 =1(1+1)2=1{\displaystyle {\frac {1(1+1)}{2}}=1}，所以这个公式在n = 1时成立。第一步完成。

第二步-推递步骤

第二步我们需要证明如果假设n = m时公式成立，那么可以推导出n = m+1时公式也成立。证明步骤如下。

我们先假设n = m时公式成立。即

1+2+⋯ ⋯ -->+m=m(m+1)2{\displaystyle 1+2+\cdots +m={\frac {m(m+1)}{2}}}（等式1）

然后在等式等号两边分别加上m + 1得到

1+2+⋯ ⋯ -->+m+(m+1)=m(m+1)2+(m+1){\displaystyle 1+2+\cdots +m+(m+1)={\frac {m(m+1)}{2}}+(m+1)}（等式2）

这就是n = m+1时的等式。我们现在需要根据等式1证明等式2成立。通过因式分解合并，等式2的右手边

=m(m+1)2+2(m+1)2=(m+2)(m+1)2=(m+1)(m+2)2=(m+1)[(m+1)+1]2.{\displaystyle ={\frac {m(m+1)}{2}}+{\frac {2(m+1)}{2}}={\frac {(m+2)(m+1)}{2}}={\frac {(m+1)(m+2)}{2}}={\frac {(m+1)[(m+1)+1]}{2}}.}

也就是说

1+2+⋯ ⋯ -->+(m+1)=(m+1)[(m+1)+1]2{\displaystyle 1+2+\cdots +(m+1)={\frac {(m+1)[(m+1)+1]}{2}}}

这样便证明了从P（m） 成立可以推导出P（m+1） 也成立。证明至此完成，结论：对于任意自然数n，P（n） 均成立。

解释

在这个证明中，归纳推理的过程如下：

首先证明P(1)成立，即公式在n = 1时成立。

然后证明从P（m） 成立可以推导出P（m+1） 也成立。（这里实际应用的是演绎推理法）

根据上两条从P(1)成立可以推导出P（1+1），也就是P(2)成立。

继续推导，可以知道P（3）成立。

从P(3)成立可以推导出P(4)也成立。

不断不断不断的重复推导下一命题成立的步骤。（这就是所谓“归纳”推理的地方）

我们便可以下结论：对于任意自然数n，P（n） 成立。

数学归纳法的变体

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

从0以外的自然数开始

第一种情况： 如果欲证明的命题并不是针对全部自然数，而只是针对所有大于等于某个数字b的自然数，那么证明的步骤需要做如下修改：

第一步，证明当n = b时命题成立。

第二步，证明如果n = m（m ≥ b） 成立，那么可以推导出n = m+1也成立。

用这个方法可以证明诸如“当n ≥ 3时，n > 2n”这一类命题。

第二种情况： 如果欲证明的命题针对全部自然数，但仅当大于等于某个数字b时比较容易证明，则可参考如下步骤：

第一步，证明当n =0，1，2，… b时命题成立。

第二步，证明如果n = m（m ≥ b） 成立，那么可以推导出n = m+1也成立。

用这种方法可以证明一些需要通过放缩来证明的不等式。

只针对偶数或只针对奇数

如果我们想证明的命题并不是针对全部自然数，而只是针对所有奇数或偶数，那么证明的步骤需要做如下修改：

奇数方面：

第一步，证明当n = 1时命题成立。

第二步，证明如果n = m成立，那么可以推导出n = m+2也成立。

偶数方面：

第一步，证明当n = 0或2时命题成立。

第二步，证明如果n = m成立，那么可以推导出n = m+2也成立。

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

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

完整归纳法

另一个一般化的方法叫完整归纳法（也称第二数学归纳法），在第二步中我们假定式子不仅当n = m时成立，当n小于或等于m时也成立.这样可以设计出这样两步:

证明当n = 0时式子成立.

证明当n ≤ m时成立，那么当n = m + 1时式子也成立.

例如，这种方法被用来证明：

其中fib（n） 是第n个斐波纳契数和Φ = (1 + 5) / 2 (即黄金分割).如果我们可以假设式子已经在当n = m和n = m − 1时成立，从fib（m + 1） = fib(m) + fib（m − 1）之后可以直截了当地证明当n=m + 1时式子成立.

这种方法也是第一种形式的特殊化：

定义P（n） 是我们将证的式子,

P（0）和P（1）成立

P（m + 1）在P（m）和P（m − 1）成立时成立。

结论：P（n）对一切自然数n成立。

超限归纳法

最后两步可以用这样一步表示：

证明如果式子在所有的n < m成立，那么式子在当n = m时也成立.

实际上这是数学归纳法的大多数通式，可以知道他不仅对表达自然数的式子有效，而且对于任何在良基集（也就是一个偏序的集合，包括有限降链） 中元素的式子也有效（这里"a < b当且仅当a ≤ b和a ≠ b）.

这种形式的归纳法当运用到序数（以有序的和一些的良基类的形式）时被称为超限归纳法.它在集合论，拓扑学和其他领域是一种重要的方法.

要区别用超限归纳法证明的命题的三种情况：

m是一个极小元素，也就是没有一个元素小于m

m有一个直接的前辈，比m小的元素有一个大的元素

m没有任何前辈，也就是m是一个界限序数.

参见数学归纳法的三种形式。

数学归纳法的合理性

数学归纳法的原理作为自然数公理，通常是被规定了的（参见皮亚诺公理）。

相关条目

归纳推理

演绎推理

结构归纳法

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。