数学归纳法

什么是数学归纳法

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

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

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

  1. 证明当n=0时命题成立。
  2. 证明如果在n=m时命题成立,那么可以推导出在n=m+1时命题也成立。(m代表任意自然数)

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

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

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

数学归纳法的应用步骤

用数学归纳法证题要恰当运用解析法,紧要有如下三个步骤:

①归纳基础:证n取第一个值时命题成立。

②证传递性:由成立证明时命题成立。

③得出结论:综合,时命题成立。

数学归纳法的举例解析

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

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

证明

第一步

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

第二步

第二步我们需要证明如果假设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)均成立。

解释

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

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

数学归纳法的变体

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

从0以外的数字开始

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

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

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

只针对偶数或只针对奇数

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

奇数方面:

  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,原命题均成立。

数学归纳法的合理性

数学归纳法的原理作为自然数公理,通常是被规范了的(参见皮亚诺公理).但是他可以用一些逻辑方式证明;比如,如果下面的公理:

自然数集是良序的。

注意到有些其他的公理确实的是数学归纳法原理中的二者择一的公式化.更确切地说,两个都是等价的.

郑重声明:东方财富网发布此信息的目的在于传播更多信息,与本站立场无关。东方财富网不保证该信息(包含但不限于文字、数据及图表)全部或者部分内容的准确性、真实性、完整性、有效性、及时性、原创性等。相关信息并未经过本网站证实,不对您构成任何投资建议,据此操作,风险自担。

扫一扫下载APP

扫一扫下载APP
信息网络传播视听节目许可证:0908328号 经营证券期货业务许可证编号:913101046312860336 违法和不良信息举报:021-61278686 举报邮箱:jubao@eastmoney.com
沪ICP证:沪B2-20070217 网站备案号:沪ICP备05006054号-11 沪公网安备 31010402000120号 版权所有:东方财富网 意见与建议:4000300059/952500