数学归纳法

维基百科,自由的百科全书
跳转至: 导航搜索

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

虽然数学归纳法名字中有“归纳”,但是数学归纳法并非不严谨归纳推理法,它是属于完全严谨的演绎推理法

定义[编辑]

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

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

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

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

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

例子[编辑]

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

1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}

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

证明[编辑]

第一步[编辑]

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

第二步[编辑]

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

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

1 + 2 + \cdots + m = \frac{m(m + 1)}{2}(等式1)

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

1 + 2 + \cdots + m + (m + 1) = \frac{m(m + 1)}{2} + (m+ 1)(等式2)

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


= \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 + \cdots + (m + 1) = \frac{(m + 1)[(m + 1) + 1]}{2}

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

解释[编辑]

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

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

数学归纳法的变体[编辑]

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

从0以外的自然数开始[编辑]

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

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

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

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

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

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

只針對偶数或只針對奇数[编辑]

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

奇数方面:

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

偶数方面:

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

递降归纳法 又名 遞迴歸納法[编辑]

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

完整归纳法[编辑]

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

  1. 证明当n = 0时式子成立.
  2. 证明当nm时成立,那么当n = m + 1时式子也成立.

例如,这种方法被用来证明:

fibn) = [Φn −(−1/Φ)n ] / 51/2

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

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

  1. 定义Pn) 是我们将证的式子,
  2. P0P1)成立
  3. Pm + 1)在Pm)和Pm − 1)成立时成立。

结论:Pn)对一切自然数n成立。

超限归纳法[编辑]

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

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

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

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

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

  1. m是一个极小元素,也就是没有一个元素小于m
  2. m有一个直接的前辈,比m小的元素有一个大的元素
  3. m没有任何前辈,也就是m是一个界限序数.

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

数学归纳法的合理性[编辑]

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

相关条目[编辑]

外部链接[编辑]