用户:Dz902/沙盒/数学归纳法

数学归纳法是一种数学证明方法,通常被用于证明某个给定命题在整个(或者局部)自然数范围内成立。除了自然数以外,广义上的数学归纳法也可以用于证明一般良基结构,例如:集合论中的。这种广义的数学归纳法应用于数学逻辑计算机科学领域,称作结构归纳法

需要留意的是,数学归纳法虽然名字中有“归纳”,但是实际上数学归纳法并不属于不严谨归纳推理法,实际上是属于完全严谨的演绎推理法

定义

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

 
骨牌一个接一个倒下,就如同一个值到下一个值的过程。
  1. 证明当 n = 0 时命题成立。
  2. 证明如果在 n = m 时命题成立,那么可以推导出在 n = m+1 时命题也成立。(m 代表任意自然数)

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

  1. 证明第一张骨牌会倒。
  2. 证明只要任意一张骨牌倒了,那么与其相临的下一张骨牌也会倒。

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

例子

假设我们要证明下面这个公式(命题):

 

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

证明

第一步

第一步证明的是这个公式在 n = 0 时成立(即 P(0) 成立)。这里要注意的是 0 = 0,而 0(0 + 1) / 2 = 0,所以这个公式在 n = 0 时成立。证明的第一步完成。

第二步

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

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

  (等式 1)

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

  (等式 2)

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

 

也就是说

 

这样便证明了从 P(m) 成立可以推导出 P(m+1) 也成立。证明至此结束,结论:对于任意自然数 n,P(n) 均成立。

解释

在这个证明中,归纳推理的过程如下:

  1. 首先证明 P(0) 成立,即公式在 n = 0 时成立。
  2. 然后证明从 P(m) 成立可以推导出 P(m+1) 也成立。(这里实际应用的是演绎推理法)
  3. 根据上两条从 P(0) 成立可以推导出 P(0+1),也就是 P(1) 成立。
  4. 继续推导,可以知道 P(2)、P(3) 也成立。
  5. 从 P(3) 成立可以推导出 P(4) 也成立。
  6. 等等等等,不断重复。(这就是所谓“归纳”推理的地方)
  7. 我们便可以下结论:对于任意自然数 n,P(n) 成立。

数学归纳法的变体

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

从 0 以外的数字开始

如果我们想证明的命题并不是针对全部自然数,而只是针对所有大于等于某个数字 b 的自然数,那么证明的步骤需要做如下修改:

  1. 第一步,证明当 n = b 时命题成立。
  2. 第二步,证明如果 n = m (mb) 成立,那么可以推导出 n = m+1 也成立。

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

相关条目

归纳推理法

演绎推理法

结构归纳法