数学归纳法证明的原理
数学归纳法证明的原理
数学归纳法证明的原理
数学归纳法证明的是与自然数有关的命题，它的依据是皮亚诺提出的自
然数的序数理论，就是通常所说的自然数的皮亚诺公理，内容是：
（１）ｌ 是自然数。
（２）每个自然数 ａ 有一个确定的“直接后继”数 ａ’，ａ 也是自然数。
（２）ａ’≠１，即 １ 不是任何自然数的“直接后继”数。
（４）由 ａ’＝ｂ’，推得 ａ＝ｂ，即每个自然数只能是另外的唯一自然的“直
接后继”数。
（５）任一自然数的集合，如果包含 １，并且假设包含 ａ，也一定包含 ａ
的“直接后继”数 ａ’，则这个集合包含所有的自然数。
皮亚诺公理中的（５）是数学归纳法的依据，又叫归纳公理
数学归纳法的应用及举例。
因为由假设知 ４２ｋ＋１＋３ｋ＋２ 能被 １３ 整除，１３４２ｋ＋１ 也能被 １３ 整除，这就
是说，当 ｎ＝ｋ＋１ 时，ｆ（ｋ＋ｌ）能被 １３ 整除。根据（１）、（２），可知命题
对任何 ｎ∈Ｎ 都成立。
下面按归纳步中归纳假设的形式向读者介绍数学归纳法的几种不同形式
以及它们的应用。
（ｌ）简单归纳法。即在归纳步中，归纳假设为“ｎ＝ｋ 时待证命题成立”。
这是最常用的一种归纳法，称为简单归纳法，大家都比较熟悉，这里不再赘
述。
（２）强归纳法。这种数学归纳法，在归纳步中，其归纳假设为“ｎ≥ｋ
时待证命题成立”。我们称之为强归纳法，又叫串值归纳法。
通常，如果在证明 ｐ（ｎ＋ｌ）成立时，不仅依赖于 ｐ（ｎ）成立，而且还
可能依赖于以前各步时，一般应选用强归纳法，下面举例说明其应用。
例 有数目相等的两堆棋子，两人轮流从任一堆里取几项棋子，但不能
不取也不能同时从两堆里取，规定凡取得最后一项者胜。求证后者必胜。
证：归纳元 ｎ 为每堆棋子的数目。设甲为先取者，乙为后取者。
奠基 ｎ＝ｌ，易证乙必胜。
归纳 设 Ｎ ｎ≤ｋ 时，乙必胜。现证 ｎ＝ｋ＋ｌ 时也是乙必胜。
设甲在某堆中先取 ｒ 颗，Ｏ＜ｒ≤ｋ。乙的对策是在另一堆中也取 ｒ 颗。有
二种可能：
（１）若 ｒ＜ｋ，经过两人各取一次之后，两堆都只有 ｋ－ｒ 颗，ｋ－ｒ＜ｋ，
现在又轮到甲先取，依归纳假设，乙必胜。
（２）若 ｒ＝ｋ，显然是乙胜，证毕。
上述形式的归纳法虽然比较简单，但如使用不当，往往会发生错误，有
两点应注意：第一，在使用归纳假设时防止无形中引入不相干的假设。第二，
在证明过程中应注意数学规律的正确性。下面我们引入一个反例，在这个反
例中，由于错误的证明导致证得了错误的待证命题。
反倒：证明任意 ｎ 条直线均能重合成一条直线。
下面给出错误的证明：
证：奠基 ｎ＝１ 时该命题成立。
归纳 利用强归纳法，可以有如下的归纳假设：任意 １ 条，２ 条，３ 条，…，
ｋ 条直线均重合成一条直线，要证 ｋ＋１ 条直线也重合成一条直线，设这 ｋ＋１
条直线为 ｌ１、ｌ２、…，ｌｋ，ｌｋ＋１ 由强归纳假设得 ｌ１，…，ｌｋ…重合为一条直线，
记为 ｌ。又由强归纳假设得 ｌ 和 ｌｋ＋１ 重合为一条直线，于是任意 ｎ 条直线便
重合一条直线了。
细心的读者也许已经发现这里的错误了，这是由于错误地使用了强归纳
假设而造成的。具体地说，这是在“ｌ 和 ｌｋ＋１ 这两条直线重合为一条直线”
这一点把强归纳假设使用错了。强归纳假设中并没有包含这一条件，因为我
们这里奠的基是 ｎ＝ｌ，因此待证命题“ｋ＋１ 条直线重合为一条直线”要求对于
一切大于等于 １ 的 ｋ 成立，而上面证明中所假设的 ｌ 和 ｌｋ＋１ 重合为一条直线
实际上是要求 ｋ≥２，这就是错误的所在。
（３）参变归纳法。在待证命题中含有参数的时候，例如 Ｐ（ｕ，ｎ），则
用数学归纳法证明 Ｐ（ｕ，ｎ）对一切 ｎ 成立时，在奠基步中，应证 Ｐ（ｕ，０）
对一切 ｕ 成立。在归纳步中，假设 Ｐ（ｕ，ｋ）对一切 ｕ 成立，证明 Ｐ（ｕ，ｋ＋１）
对一切 ｕ 成立。这里，“Ｐ（ｕ，ｋ）”对一切 ｕ 成立称之为参变归纳假设，这
种证明方法叫做参变归纳法，Ｕ 起着参数的作用。
例 求证当 ｎ≥３ 时有 ｎ（ｎ＋１）≥（ｎ＋１）３。
本题证明的困难主要在于归纳步骤，无论采用哪种归纳假设，都难于证
明。如果我们对该待证命题施展一定的技巧，把该式中的部分 ｎ 写成 ｕ（视
作参数），部分 ｎ 保持不变，即写成
ｎｕｎ≥（ｕ＋ｌ）ｎ，
则可用参变归纳法证明当 ｕ≥ｎ≥３ 时上式成立，原命题即可得证。
奠基 ｎ＝３ 时，对 ｕ≥３ 的一切 ｕ 均有
右端＝３ｕ３＝ｕ３＋ｕｕ２ｕ
≥ｕ３＋３ｕ＋ｇｕ
＞ｕ３＋３ｕ２＋３ｕ＋１
＝（ｕ＋１）３＝右端
归纳 ｎ＝ｋ＋１ 时，
左端＝（ｋ＋１）Ｕｋ＋１＝ｕ（ｋ＋１）ｕｋ
＝（ｕｋ 十 ｕ）ｕｋ≥（ｕｋ 十 ｋ）Ｕｋ
＝ｋ（ｕ＋ｌ）ｕｋ≥（ｎ＋１）（ｕ＋１）ｋ
＝（Ｕ＋ｌ）ｋ＋１＝右端。
所以当 ｕ≥ｎ≥３ 时，有 ｎｕｎ＞（ｕ＋ｌ）ｎ。
令 ｕ＝ｎ，上式便为 ｎｎ＋１≥（ｎ＋ｌ）ｎ，即为原不等式，故原不等式得证。
值得指出的是，上面三种形式的数学归纳法，都要求待证命题含有自然
数变元 ｎ，对 ｎ 施行归纳，ｎ 称为归纳变元，但是在数学的一些分支中，有些
待证命题表面上看来似乎不含自然数变元 ｎ，但仔细一分析，实际上是含有
自然数变元的，当我们一旦把 ｎ 的含义明确以后，用数学归纳法去证明这些
待证命题就迎刃而解了。举一个简单的例子。
例 证明由｛ａ，ｂ，ｃ，ｄ｝四个标识符利用＋、－运算符组成的任意算术
表达式中，所含标识符的个数一定等于这个表达式中运算符的个数加 １。
证：设任意的表达式为 ｆ，而归纳变元 ｎ 为 ｆ 中所含运算符的个数。
奠基 ｎ＝０，则 ｆ 由一个标识符组成（因为没有运算符），所以命题成立。
归纳 假设 ｎ≤ｋ 时本命题成立，现证 ｎ＝ｋ＋１ 时本命题也成立。 ｆ 一
定是下述两种情况之一：
ｆ 是 ｆ１＋ｆ２ 或 ｆ 是 ｆ１－ｆ２。
其中 ｆ１，ｆ２ 所含的运算符个数都小于 ｋ＋ｌ，对 ｆ１，ｆ２ 使用归纳假设，可
得 ｆ１＋ｆ２，ｆ１－ｆ２ 中所含标识符个数也比各自所含的运算符的个数多 １。
（４）广义归纳法。数学归纳法不仅可用于含有自然数变元 ｎ 的命题，经
推广后，还可用于含有某些其它集合上的命题。这种集合，称为归纳集。对
于一个含有某个归纳集上的变元 ｘ 的待证命题 Ｐ（ｘ），所用的归纳法称之为
广义归纳法。
定义：设有一个集合 Ａ，如果它满足下面三个性质：
（１）ａ１，ａ２…，ａｎ 是 Ａ 中的元素（ｎ≥１）；
（２）如果 ｘ 是 Ａ 中元素，则 ｆ１１（ｘ），ｆ１２（ｘ），…ｆ１ｎ１（ｘ）也是 Ａ 中
的元素（ｎ、＞０）；
如果 ｘ，ｙ 是 Ａ 是元素，则 ｆ２１（ｘ、ｙ），ｆ２２（ｘ，ｙ），…ｆ２ｎ２（ｘ，ｙ）
也是 Ａ 中元素（ｎ２＞０）；…；
如果 ｘ１…，ｘｍ 是 Ａ 中元素，则 ｆｍ１ ｘｌ…ｘｍ），ｆｍ２（ｘｌ…，ｘｍ），…ｆｍｎｍ
（ｘ１…，ｘｍ）也是 Ａ 中元素（ｍ≥ｌ，ｎｍ＞０）。
（３）Ａ 中的元素仅限于此。
则 Ａ 称之为归纳集 ａ１，ａ２，…ａｎ 称为该集的开始元素，诸 ｆｉｊ 称为该集
的生成函数（其中第一下标为该函数的元素，第二下标以区分具有同样元素
的各函数）。
按照上述的定义，自然数集是归纳集，它的开始元素是 ０，生成函数是 ｆ
（ｘ）＝ｘ＋１。
前例中集｛ａ，ｂ，ｃ，ｄ｝的元素利用“＋”，“－”运算所构成的一切表
达式的集合是归纳集，开始元素是是 ａ，ｂ，ｃ，ｄ，生成函数为 ｆ２１（ｘ，ｙ）
＝ｘ＋ｙ，ｆ２２（ｘ，ｙ）＝ｘ－ｙ。
在证明含有某个归纳集 Ａ 上的变元 Ｘ 的待证命题 Ｐ（ｘ）时，可用如下的
广义归纳法。
奠基步要证明（ａｌ），Ｐ（ａ２），……Ｐ（ａｎ）成立，这里 ａｌ，ａ２…，ａｎ
是 Ａ 中的开始元素。
归纳法要证明对于 １≤ｉ≤ｍ 及 １≤ｊ≤ｎ 的所有 ｉ、ｊ 对于 Ａ 中的任何元
素 ｘ１，ｘ２…，ｘｉ，如果 Ｐ（ｘｌ），Ｐ（ｘ２），…，Ｐ（ｘ１）成立，则 Ｐ（ｆｉｊ（ｘｘ１，…，
ｘｉ））也成立。在例 ４ 中，因为表达式所组成的集合是归纳集（记为 Ａ），
我们可用广义归纳法证之。
奠基：对于 Ａ 中的四个开始元素 ａ，ｂ，Ｃ，ｄ，因为它们的标识符个数为
１， 而运算符个数均为 ０，所以命题成立。
归纳：对于 Ａ 中的元素 ｘ，ｙ，ｆ２１（ｘ，ｙ）＝ｘ＋ｙ 中，我们设 ｘ＋ｙ 标识
符个数为 ｍ，运算符个数为 ｎ；
ｘ 中标识符个数为 ｍｌ，运算符个数为 ｎｌ；
ｘ 中标识符个数为 ｍ２，运算符个数为 ｎ２；
则
ｍ＝ｍｌ＋ｍ２＝（ｎ１＋１）＋（ｎ２＋１）
（ｎｌ＋ｎ＋１）＋１＝ｎ＋１．
同理可证 ｆ２２（ｘ，ｙ）＝ｘ－ｙ 也有如上的结果，故依广义归纳法，本命题
成立。
【数学归纳法证明的原理】相关文章：
初中数学几何证明的口诀03-25
关于血糖检测的原理总结03-09
阿基米德原理教案（通用7篇）06-30
计算机的组成原理教案（精选10篇）08-17
死亡证明的办理方法02-08
同意报考证明（精选20篇）04-15
医保卡证明及就医流程10-28
证明勾股定理的4种方法01-27
教你如何写证明信09-21
不等式的证明方法以及例解10-26