百科首页 > 正文

数学归纳法（用于数学证明的演绎推理法）

146次浏览 | 更新时间：2023-07-06

来源：网络整理

精选百科

本文由作者推荐

小编整理：

数学归纳法是一种演绎推理方法，用于证明某个给定命题在整个（或者局部）自然数范围内成立。这种方法基于一个递归证明策略，其中需要证明两个步骤：首先，对于所有的自然数n，证明当n=1时命题成立；其次，对于任意自然数n，假设当n=k时命题成立，证明当n=k+1时命题也成立。通过这两个步骤的证明，可以推断出当n属于自然数时命题成立。除了自然数以外，广义上的数学归纳法也可以用于证明一般良基结构，例如：集合论中的树。这种广义的数学归纳法应用于数学逻辑中，可以用于证明许多数学定理和公式。总之，数学归纳法是数学证明中一种非常重要的方法，可以用于证明许多数学定理和公式。它基于递归证明策略，通过证明两个步骤来推断出整个自然数范围内命题成立。这种方法在数学和其他领域中广泛应用，并且在数学逻辑中也扮演着重要的角色。

数学归纳法

用于数学证明的演绎推理法

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

基本信息

中文名	数学归纳法
外文名	mathematical induction
类型	数学证明方法
原理	自然数公理
属于	演绎推理法
适用范围	数学
公布时间	1993年

收起

简介

在数论中，数学归纳法是以一种不同的方式来证明任意一个给定的情形都是正确的（第一个，第二个，第三个，一直下去概不例外）的数学定理。

虽然数学归纳法名字中有“归纳”，但是数学归纳法并非不严谨的归纳推理法，它属于完全严谨的演绎推理法。事实上，所有数学证明都是演绎法。

解题

原理

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

证明当
时命题成立。
假设
时命题成立，那么可以推导出在
时命题也成立。（m代表任意自然数）

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

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

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

解题要点

数学归纳法对解题的形式要求严格，数学归纳法解题过程中，

第一步：验证n取第一个自然数时成立

第二步：假设

时成立，然后以验证的条件和假设的条件作为论证的依据进行推导，在接下来的推导过程中不能直接将

代入假设的原式中去。

最后一步总结表述。

需要强调是数学归纳法的两步都很重要，缺一不可，否则可能得到下面的荒谬证明：

证明1：所有的马都是一种颜色

首先，第一步，这个命题对

时成立，即，只有1匹马时，马的颜色只有一种。

第二步，假设这个命题对n成立，即假设任何n匹马都是一种颜色。那么当我们有

匹马时，不妨把它们编好号：

对其中（1、2……n）这些马，由我们的假设可以得到，它们都是同一种颜色；

对

这些马，我们也可以得到它们是一种颜色；

由于这两组中都有（2、3、……n）这些马，所以可以得到，这

种马都是同一种颜色。

这个证明的错误来于推理的第二步：当

时，

，此时马的编号只有1、2，那么分的两组是（1）和（2）——它们没有交集，所以第二步的推论是错误的。数学归纳法第二步要求

过程对

的数都成立，而上面的证明就好比多米诺骨牌的第一块和第二块之间间隔太大，推倒了第一块，但它不会推倒第二块。即使我们知道第二块倒下会推倒第三块等等，但这个过程早已在第一和第二块之间就中断了。

证明2：举例证明下面的定理

——等差数列求和公式

第一步，验证该公式在

时成立。即有

，所以这个公式在

时成立。

第二步，需要证明假设

时公式成立，那么可以推导出

时公式也成立。步骤如下：

假设

时公式成立，即

（等式1）

然后在等式两边同时分别加上

得到

（等式2）

这就是

时的等式。我们下一步需要根据等式1证明等式2 成立。通过因式分解合并，等式2的右边

也就是

这样我们就完成了由

成立推导出

成立的过程，证毕。

结论：对于任意自然数n，公式均成立。

对于以上例2的分析

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

首先证明
成立。
然后证明从
成立可以推导出
也成立（这里实际应用的是演绎推理）。
根据上两条从
成立可以推导出
，也就是
成立。
继续推导，可以知道
成立。
从
成立可以推导出
也成立……
不断重复3的推导过程（这就是所谓“归纳”推理的地方）。
我们便可以下结论：对于任意非零自然数n，公式成立。

合理性

数学归纳法的原理，通常被规定作为自然数公理（参见皮亚诺公理）。但是在另一些公理的基础上，它可以用一些逻辑方法证明。数学归纳法原理可以由下面的良序性质（最小自然数原理）公理可以推出：

自然数集是良序的。（每个非空的正整数集合都有一个最小的元素）

比如

这个正整数集合中有最小的数——1.

下面我们将通过这个性质来证明数学归纳法：

对于一个已经完成上述两步证明的数学命题，我们假设它并不是对于所有的正整数都成立。

对于那些不成立的数所构成的集合S，其中必定有一个最小的元素k。（1是不属于集合S的，所以

）

k已经是集合S中的最小元素了，所以

是不属于S，这意味着

对于命题而言是成立的——既然对于

成立，那么也对k也应该成立，这与我们完成的第二步骤矛盾。所以这个完成两个步骤的命题能够对所有n都成立。

注意到有些其它的公理确实是数学归纳法原理的可选的公理化形式。更确切地说，两者是等价的。

变体

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

从0以外的数字开始

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

第一步，证明当

时命题成立。第二步，证明如果

成立，那么可以推导出

也成立。

用这个方法可以证明诸如“当

时，

”这一类命题。

针对偶数或奇数

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

奇数方面：

第一步，证明当

时命题成立。第二步，证明如果

成立，那么可以推导出

也成立。

偶数方面：

第一步，证明当

或2时命题成立。第二步，证明如果

成立，那么可以推导出

也成立。

递降归纳法（又称递归归纳法）

数学归纳法并不是只能应用于形如“对任意的n”这样的命题。对于形如“对任意的

”这样的命题，如果对一般的n比较复杂，而

比较容易验证，并且我们可以实现从k到

的递推，

的话，我们就能应用归纳法得到对于任意的

，原命题均成立。如果命题P(n)在

时成立，并且对于任意自然数k，由

成立，其中t是一个常量，那么P(n)对于一切自然数都成立.

跳跃归纳法

设P(n)表示一个与自然数n有关的命题，若(1)P(1)，P(2),…,P(l)成立;(2)假设P(k)成立，可以推出

成立，则P(n)对一切自然数n都成立.

第一数学归纳法

一般地，证明一个与自然数n有关的命题P(n)，有如下步骤：

（1）证明当n取第一个值n0时命题成立。

对于一般数列取值为0或1，但也有特殊情况；

（2）假设当

（

，k为自然数）时命题成立，证明当

时命题也成立。

综合（1）（2），对一切自然数

，命题P(n)都成立。

第二数学归纳法（完整归纳法）

另一个一般化的方法叫完整归纳法（也称第二数学归纳法），在第二步中我们假定式子不仅当

时成立，当n小于或等于m时也成立。这样可以设计出这样两步:

证明当
时式子成立.
假设当
时成立，证明当
时式子也成立.

则命题成立。

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

其中fib(n)是第n个斐波纳契数和

。

(即黄金分割)。如果我们可以假设式子已经在当

和

时成立，从

之后可以直截了当地证明当

时式子成立。

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

定义P(n) 是我们将证的式子,
P(0)和P(1)成立
在P（m）和
成立时成立。

结论：P(n)对一切自然数n成立。

倒推归纳法

又名反向归纳法

（1）验证对于无穷多个自然数n命题P(n)成立（无穷多个自然数可以是一个无穷数列中的数，如对于算术几何不等式的证明，可以是

，

）；

（2）假设

成立，并在此基础上，推出P(k)成立，

综合（1）（2），对一切自然数

，命题P(n)都成立；

螺旋式归纳法

对两个与自然数有关的命题P(n)，Q(n)，

（1）验证

时P(n)成立；

（2）假设

成立，能推出Q(k）成立，假设 Q(k)成立，能推出

成立；

综合（1）（2），对一切自然数

，P(n)，Q(n)都成立。

发展历程

已知最早的使用数学归纳法的证明出现于Francesco Maurolico的Arithmeticorum libri duo（1575年）。Maurolico利用递推关系巧妙地证明出前n个奇数的总和是

，由此总结出了数学归纳法。

最简单和常见的数学归纳法证明方法是证明当n属于所有正整数时一个表达式成立，这种方法是由下面两步组成：

递推的基础：证明当

时表达式成立。

递推的依据：证明如果当

时成立，那么当

时同样成立。

这种方法的原理在于第一步证明起始值在表达式中是成立的，然后证明一个值到下一个值的证明过程是有效的。如果这两步都被证明了，那么任何一个值的证明都可以被包含在重复不断进行的过程中。

数学归纳法相关的文章

被嫌弃的松子的一生（2006年中岛哲也执导的歌舞剧情片）

电影《被嫌弃的松子的一生》（日语：嫌われ松子の一生）改编自山田宗树所著同名小说，由中岛哲也编剧、导演，石田雄治、佐谷秀美、间濑泰宏、小玉圭太等主演，于2006年5月27日在日本首映。

多疑

多疑是指神经过敏、疑神疑鬼的消极心态，属于精神心理科疾病。与生活环境、消极暗示、受过伤害等有关，因心理脆弱而过度自我保护。多疑分为内应多疑和外应多疑。内应多疑的主要表现为总是怀疑某人对自己不好，某件事对自己不利，便耿耿于怀，闷闷不乐，情绪立即反常，半天都不能排解；外应多疑的主要表现为的觉得被人怀疑后

黑山（欧洲的议会制共和制国家）

黑山(黑山语:Crna Gora，英语：Montenegro，塞尔维亚语：ЦрнаГора，即"黑色的山")，是位于巴尔干半岛西南部、亚得里亚海东岸的一个多山国家。黑山东北部与塞尔维亚毗连，东部为科索沃，东南部与阿尔巴尼亚接壤，西北部与波黑及克罗地亚交界，西南部濒临亚得里亚海，海岸线长293公里。气

日照市（中国山东省辖地级市）

日照市，中国山东省下辖地级市，地处东经119°04′一119°39’，北纬35°04’一35°36‘。位于山东省东南部，东濒黄海，西邻莒南、莒县，北接五莲、胶南县，南靠江苏省赣榆县，境内南北长59.8千米；东西宽57.95千米，海岸线长226.35千米，总面积10947平方千米，截至2022年末，日

提比略·恺撒·奥古斯都（罗马帝国第二位皇帝）

提比略·恺撒·奥古斯都罗马帝国第二位皇帝提比略，全名提比略·恺撒·（神君奥古斯都之子·）奥古斯都（拉丁语：Tiberius Caesar Divi Augusti filius Augustus，公元前42年11月16日—公元37年3月16日），原名提比略·克劳狄乌斯·尼禄或提比略·尤里乌斯·恺撒（Tiberius Claudius Nero或Tiberius Julius Caesar），中文又

北德维纳河（位于俄罗斯北部的河）

北德维纳(Северная Двина)河位于俄罗斯北部，由苏霍纳(Сухона)河和尤格(Юг)河汇流而成，向西北流，最后流入白海的德维纳湾。干流全长744千米，若以苏霍纳河为源计算，河长1332千米，流域面积35.7万平方千米。由源地至维切格达(Вычегда)河口，称小北德维纳(Малая Сев．Двина)河。河口多年平均流量3490立方米/秒，径流量1100亿立方米。