1.5 归纳法原理与反归纳法

数学归纳法的发展及其在数学中的应用摘要：在数学论证中，数学归纳法是一种常用的数学方法，用途很广，对于某些结论是自然数的函数命题，往往都可以通过数学归纳法来加以证明。

本文叙述了数学归纳法名称的发展，数学归纳法内容的发展，并分别从良序原理、数学归纳法、第二数学归纳法、数学归纳法的有效性这四个方面对数学归纳法的原理做了介绍，都有相关的例子，能帮助读者深入的理解数学归纳法的原理。

本文也列举了几种常见的数学归纳法的形式，如第一数学归纳法、第二数学归纳法、倒推归纳法、螺旋式归纳法。

在了解数学归纳在数学中的应用后，本文重点叙述了数学归纳法在证明恒等式、证明不等式、证明整除问题、证明几何问题、探索与正整数有关的问题中的具体应用过程。

通过本文，能使读者更加深入的了解数学归纳法，并且能更好的运用数学归纳法解决数学学科中的一些问题。

关键词：数学归纳法发展原理应用一、数学归纳法的发展（一）数学归纳法名称的发展“数学归纳法”名称是由英国数学家创立, 并由英国教科书作者普遍采用推广。

在名称上迈出重要一步的是英国数学家德摩根。

1838年在伦敦出版的《小百科全书》中，德摩根在他的条目“归纳法里建议使用“逐收归纳法”。

但在该条目的最后他偶然地使用了术语数学归纳法，这是我们所能看到这一术语的最早使用。

无论是毛罗利科还是帕斯卡，也无论是伯努利还是其后的数学家们，虽然都在不断地使用数学归纳法，但在很长的时期内并授有给他们的方法以任何名称。

只是由于沃利斯以及雅各布·伯努利的工作，才引进了“归纳法”这一名称。

并在两种截然不同的意义上应用于数学：(1)以特此获得一般结论的沃利斯方式(2)指定的步骤论证，并且影响了其后的数学家们，使这种混用状态大约持续了140年。

到l9世纪上半叶，英国的数学家皮科克在他的《代数学》的排列与组合部分，谈到梅成的规律用归纳法延伸到任意数，是从预攫 f 意义上以沃利斯方式使用归纳法的。

后来，他又将从“到R+1的论证称之为证明归纳法。

数学归纳法证明的原理数学归纳法证明的原理数学归纳法证明的原理数学归纳法证明的原理数学归纳法证明的是与自然数有关的命题，它的依据是皮亚诺提出的自然数的序数理论，就是通常所说的自然数的皮亚诺公理，内容是：（１）ｌ是自然数。

（２）每个自然数ａ有一个确定的“直接后继”数ａ’，ａ也是自然数。

（２）ａ’≠１，即１不是任何自然数的“直接后继”数。

（４）由ａ’＝ｂ’，推得ａ＝ｂ，即每个自然数只能是另外的唯一自然的“直接后继”数。

（５）任一自然数的集合，如果包含１，并且假设包含ａ，也一定包含ａ的“直接后继”数ａ’，则这个集合包含所有的自然数。

皮亚诺公理中的（５）是数学归纳法的依据，又叫归纳公理数学归纳法的应用及举例。

因为由假设知４２ｋ＋１＋３ｋ＋２能被１３整除，１３４２ｋ＋１也能被１３整除，这就是说，当ｎ＝ｋ＋１时，ｆ（ｋ＋ｌ）能被１３整除。

根据（１）、（２），可知命题对任何ｎ∈Ｎ都成立。

下面按归纳步中归纳假设的形式向读者介绍数学归纳法的几种不同形式以及它们的应用。

（ｌ）简单归纳法。

即在归纳步中，归纳假设为“ｎ＝ｋ时待证命题成立”。

这是最常用的一种归纳法，称为简单归纳法，大家都比较熟悉，这里不再赘述。

（２）强归纳法。

这种数学归纳法，在归纳步中，其归纳假设为“ｎ≥ｋ时待证命题成立”。

我们称之为强归纳法，又叫串值归纳法。

通常，如果在证明ｐ（ｎ＋ｌ）成立时，不仅依赖于ｐ（ｎ）成立，而且还可能依赖于以前各步时，一般应选用强归纳法，下面举例说明其应用。

例有数目相等的'两堆棋子，两人轮流从任一堆里取几项棋子，但不能不取也不能同时从两堆里取，规定凡取得最后一项者胜。

求证后者必胜。

证：归纳元ｎ为每堆棋子的数目。

设甲为先取者，乙为后取者。

奠基ｎ＝ｌ，易证乙必胜。

归纳设Ｎｎ≤ｋ时，乙必胜。

现证ｎ＝ｋ＋ｌ时也是乙必胜。

设甲在某堆中先取ｒ颗，Ｏ＜ｒ≤ｋ。

乙的对策是在另一堆中也取ｒ颗。

有二种可能：（１）若ｒ＜ｋ，经过两人各取一次之后，两堆都只有ｋ－ｒ颗，ｋ－ｒ＜ｋ，现在又轮到甲先取，依归纳假设，乙必胜。

数学归纳法及其应用发表时间：2019-01-23T16:43:27.747Z 来源：《教育学》2019年1月总第166期作者：折小妹[导读] 数学归纳法是数学证明的一种重要工具，它常用来证明与自然数有关的命题。

陕西省大柳塔第一小学719315摘要：数学归纳法是一种证明与正整数有关命题的极为有效的科学方法。

本文主要对数学归纳法的原理与方法、理论与应用进行分析，并介绍了数学归纳法在数学整除问题、数列、不等式以及几何等问题中的应用。

关键词：数学归纳法数列不等式一、数学归纳法的概述1.归纳法与数学归纳法。

（1）归纳法。

①完全归纳法。

②不完全归纳法。

③典型归纳推理。

（2）数学归纳法。

数学归纳法是数学证明的一种重要工具，它常用来证明与自然数有关的命题。

它基于自然数的一个重要性质：任意一个自然数的集合，如果包含数1，并且假设包含数k，也一定包含k的后继数k+1，那么这个集合包含所有的自然数。

这一重要性质，为解决有限与无限的矛盾提供了理论依据。

也就是说，如果能证明：①当n=1时命题成立。

②假设当n=k时命题成立，有n=k+1时命题成立。

那么我们就能由n=1时命题成立，推出n=1+1=2时命题成立；由n=2时命题成立，推出n=2+1=3时命题也成立；如此继续下去，虽然我们没有对所有的自然数一一逐个加以验证，但根据自然数的重要性质，实质上已经对所有的自然数做了验证。

这样的证明方法叫作数学归纳法，可见数学归纳法是一种完全归纳法。

2.数学归纳法的基础。

严格意义上的数学归纳法产生于16世纪以后，意大利数学家莫罗利科首先对与自然数有关的命题做了深入考察。

递归推理的思想方法是指：它首先确定命题对于第一个自然数是正确的，然后再证明命题对于以后的自然数具有递推性，即如果一个命题对于第一个自然数是正确的，那么作为一种逻辑必然，它对于该数的后继数也是正确的。

3.数学归纳法的原理。

数学归纳法所根据的原理是正整数集的一个最基本的性质——最小数原理。

数学归纳法的七种变式及其应用1 引言数学归纳法是数学中关于自然数命题的主要证明方法．学会并熟练运用这种方法，不仅可以帮助我们学习有关自然数的命题，而且还可以使我们更有力地解决相关问题．一般地说，与正整数有关的恒等式、不等式、数的整除性、数列的通项及前n 项和等问题，都可以用数学归纳法解决．这种方法的难点在于由n k =时成立，去证1n k =+时成立．很多情形下用常规的方法由n k =成立时，去推1n k =+成立会走进死胡同，这时须另辟他径，完成证明．本文旨在通过对数学归纳法的主要七种变式加以剖析，以及一些证法技巧的介绍，使初学者提高对数学归纳法的认识和应用能力．2 数学归纳法的原理和定义 2.1 数学归纳法的原理[1](36)P假定对一切自然数n ，我们有一个命题，设为()M n ．如果下面两条成立： （1） (1)M 是真命题；（2） 对于任意的k ，()M k 是真命题蕴含着(1)M k +是真命题，则对一切自然数n 命题()M n 为真命题．2.2 数学归纳法的定义当0n n =时某命题正确，若在n k =正确的情况下，能推出1n k =+也正确，便可递推下去．虽然我们没有对所有的自然数逐一的加以验证，但事实上这种递推就已经把所有自然数都验证了．这种方法就是数学归纳法．其步骤是： （1） 验证当0n n =时某命题正确（2） 假设n k =时，命题正确，从而推出当1n k =+时命题也正确．因此原命题正确．其中第一步是递推的基础，解决了特殊性；第二步是递推的依据，解决了从有限到无限的过度，这两步缺一不可，若只有第一步，则属于不完全归纳法；若只有第二步，则失去了假设的基础．对于1n k =+时的证明是整个数学归纳法的重点和难点．3 数学归纳法的七种变式和应用3.1 第一数学归纳法3.1.1 这种方法是我们运用最多的，也是应用最广泛的一种方法．其步骤为[2](18)P ：（1） 奠基步骤：证明当n 取第一个允许值0n 时，结论正确 ．注意0n 不一定是1，也可能是其他的自然数．（2） 递推步骤：假设当n k =（0,k N k n ∈>）时结论正确，并以此来证明1n k =+时结论也正确．由步骤（1）、（2）得出结论：命题对于从0n 开始的一切自然数均成立． 3.1.2 例题解析 例1 求证1111223(1)1nn n n ++⋅⋅⋅+=⨯⨯++ （n N ∈） 证明 （１） 当1n =时，111211=⨯+这显然是成立的． （２） 假设n k =时命题正确；即：1111223(1)1kk k k ++⋅⋅⋅+=⨯⨯++ 则当1n k =+时，11111223(1)(1)(2)k k k k ++⋅⋅⋅++⨯⨯+++ 11(1)(2)k k k k =++++ (2)11(1)(2)2k k k k k k +++==+++所以，对于所有的自然数n ，等式都成立．例2 求证 111111234212n n -+-+⋅⋅⋅+--111()122n N n n n=++⋅⋅⋅+∈++ 证明 （１） 当1n =时；左边11112211-===+右边． （２） 假设n k =时等式成立，即：111111234212k k -+-+⋅⋅⋅+--111122k k k=++⋅⋅⋅+++ 当1n k =+时，左边1111111(1)2342122122k k k k =-+-+⋅⋅⋅+-+--++11111()1222122k k k k k =++⋅⋅⋅++-++++ 111112322122k k k k k =++⋅⋅⋅+++++++=右边 即1n k =+时等式成立 ．由（１）（２）得对于一切*n N ∈等式成立．例3 设n N ∈用数学归纳法证明：224621n n n +++⋅⋅⋅+=++ 证明 假设当n k =时等式成立，即 224621k k k +++⋅⋅⋅+=++ 那么，当1n k =+时，有24622(1)k k +++⋅⋅⋅+++ 212(1)k k k =++++ 2(1)(1)1k k =++++ 这就是说当 1n k =+时等式成立．所以，n N ∈时，224621n n n +++⋅⋅⋅+=++成立．剖析 这是一种错证，缺少第一步．实际上当1n =时等式不成立，题目本身是个错题．不要以为第一步“当1n =时等式成立”无关紧要，可有可无，缺少第一步相当于失去了归纳基础，缺少第一步也会导出荒谬的结论，例如可以证出所有自然数都相等的结论．事实上，假定1k k =+成立，两边各加1就会得出：12k k +=+由此可得出全体自然数相等！例4 1n <+ (*)n N ∈．证明 （1） 当1n =11<+，不等式成立．（2） 假设当n k =1k <+成立那么，当1n k =+2(1)1k k <=+=++这就是说，当1n k =+时成立．综合（1）（2）知原不等式对(*)n N ∈成立．剖析 这种证法是错误的，在数学归纳法的第二步中，在推证1n k =+时命题也成立的时候必须把归纳假设即n k =时的命题作为条件用上，否则就不是数学归纳法了．正解 （1） 当1n =11<+不等式成立．（2） 假设当n k =1k <+，也就是22(1)k k k +<+那么，当1n k =+<2(1)1k k <=+=++就是说，当1n k =+时不等式也成立． 综合（1）（2）知原不等式对n N ∈成立． 3.2 第二数学归纳法 3.2.1[2](58)P 通过仔细学习数学归纳法原理，不难发现，如果将归纳假设改写成“假设当n k≤时，命题成立”，那里的证明仍可通过，这就启发我们在必要的时候，可以将归纳假设中的“n k =”改写为“n k ≤”事实上在很多问题的证明中，我们就是这么做的．这种假设形式的数学归纳法称作第二数学归纳法．3.2.2 例题剖析 例５[2](60)P 证明每一个正整数都可以表示成互不相同的斐波那契数列之和．证明 首先来看一下关于斐波那契数列，所谓的斐波那契数列是按照法则：12211,(1)n n n M M M M M n ++===+≥所定义的数列．当1n =时，有11M =知原命题成立．假设当n k ≤时，命题成立，要证对1n k =+时命题成立，也就是要证明1k +可以表示成不同的斐波那契数列之和．观察斐波那契数列可发现从3M 开始斐波那契数列严格单调上升，故知存在m 使：11m m M k M +≤+<，如果1m k M +=则命题成立；如果1m k M +>，则有01m k M k <+-≤由于1m k M +-是一个不超过k 的自然数，所以由归纳假设知对其命题成立，即可将它表示成互不相同的斐波那契数列之和．又因为111m m m m k M M M M +-+-<-=所以用以表示(1)m k M +-的斐波那契数均小于1m M -，因此都不与m M 相同，当将1k +写成m M 与这些数的和之后，即得到了1n k =+时的命题，可见对1n k =+，命题也成立，所以对一切自然数n 命题都成立．在这里，由于我们是对(1)m k M +-使用归纳假设而(1)m k M +-并不一定就等于k ，而是有可能小于k ．所以若采用“n k =”的归纳假设形式就会很麻烦了．例6 已知对一切,0,n n N a ∈>且3211()nnjj j j aa ===∑∑，证明 n a n =．证明 当1n =时由3211a a =及0n a >，知11a =，命题成立．假设当n k ≤时，命题已成立，即有,1,2,,j a j j k ==⋅⋅⋅．要证，也有11k a k +=+，此时，一方面有：3333121k k a a a a +++⋅⋅⋅++23121()k k a a a a +=++⋅⋅⋅++，另一方面有 3333121k k a a a a +++⋅⋅⋅++2121()k k a a a a +=++⋅⋅⋅++22121121()2()k k k k a a a a a a a a ++=++⋅⋅⋅++++⋅⋅⋅++ 比较上述两式：即得：32111212()k k k k a a a a a a +++=++⋅⋅⋅++将121,2,,k a a a k ==⋅⋅⋅=代入其中，得到32111(1)k k k a k k a a +++=++又因为1k a +0>故由上式可得211(1)0k k a a k k ++--+=解此方程，得到11k a k +=+或1k a k +=-．由于10k a +>知1k a k +=-（舍）．因此：1k a k +=+1从而知1n k =+时，命题也成立，所以对一切自然数都有n a n =．本题采用“n k ≤”的假设，在通过方程求解1k a +的过程中我们首先遇到的化简方程的问题，而这里面首先就是一个对12k a a a ++⋅⋅⋅+求和的问题，为了求出这个和数，离开了“命题已对n k ≤全都成立”的假设，问题就不好解决了．3.3 逆向数学归纳法 3.3.1这种命题的表述为[3](185)P ：如果： （1） 对任一自然数n ，总有0n n ≥使0()p n 真．（2） ()p k 真⇒(1)p k -真． 那么，()p n 对一切自然数n 真．这种方法也可以形象地称为“留空回填”第一步证明了有无数个自然数n x 使()n p x 真（1,2,3n =⋅⋅⋅）剩下的就是()1,n n x x -上的自然数尚未证明，再由第二步，有()n p x 真⇒ (1)n p x -真⇒ … ⇒ 1(1)n p x -+真，这就把“空”填上了，所以这里的逆向倒推暗藏着正向推进的一面．3.3.2 例题解析例7 求证n 个非负数的几何平均数不大于它们的算术平均数． 证明分析 n 个非负数的几何平均数是112()nn a a a ⋅⋅⋅ 算术平均数是12na a a n++⋅⋅⋅+本题就是证明：11212()nnn a a a a a a n++⋅⋅⋅+⋅⋅⋅≤（1）证明 当1n =是，（1）式显然是成立的，如果12,,,n a a a ⋅⋅⋅里面有一个等于0，（1）式也是成立的．当2n =时，（1）式是112212()2a a a a +≤ 这可以由112212()0a a -≥推出，现在我们来证明当2pn =，p 是任意自然数的时候，定理都是成立的．假设当2kn =的时候（1）式是成立的，那么1112122()k k a a a ++⋅⋅⋅111122212221222[()()]kkkkkk a a a a aa +++=⋅⋅⋅⋅⋅⋅11122122212221[()()]2k kk kkk a a a a aa +++≤⋅⋅⋅+⋅⋅⋅1122212221[]222k kkk k ka a a a a a +++++⋅⋅⋅+++⋅⋅⋅+≤+112212k k a a a ++++⋅⋅⋅+= 所以当12k n +=的时候（1）式也成立．因此当2pn =，p 是任何自然数的时候（1）式都是成立的．进一步在推到一般的n ，我们在假设当n k =的时候（1）式成立的前提，下面来证明：当1n k =-时，它也成立． 取1211k k a a a a k -++⋅⋅⋅+=-，因为当n k =的时候（1）式是成立的．所以1211k a a a k -++⋅⋅⋅+-121k ka a a a k-++⋅⋅⋅++=1121()k k k a a a a -≥⋅⋅⋅1121121[]1k k k a a a a a a k --++⋅⋅⋅+=⋅⋅⋅-两边同时除以1121[]1k k a a a k -++⋅⋅⋅+-得11121121[]()1k k k k k a a a a a a k ---++⋅⋅⋅+≥⋅⋅⋅- 由此得11211121()1k k k a a a a a a k ---++⋅⋅⋅+≥⋅⋅⋅- 即得所证． 至此命题已得到了完全的证明．3.4 有限项数学归纳法 3.4.1 这一证法的步骤是[3](183)P ：设m 为一给定的自然数如果：（1） (1)p 真；（2） ()p k 真(1)k m ≤<(1)p k ⇒+真； 那么()p n 对不超过m 的自然数n 真． 3.4.2 例题解析例8 已知,m n N ∈且3n m ≥≥ 求证：(1)mmmn n ≥+．证明 对m 用数学归纳法．（1） 当3m =时，33332323326331(1)n n n n n n n n n =+≥+>+++=+命题成立． （2） 设m k n =<命题成立．即(1)k k kn n ≥+ 则1(1)(1)()()k k k k k n k nn kn n kn k n ++=+=+≥+1(1)(1)(1)(1)k k k n kn n n n +=+>++=+这表明1m k =+时命题成立．所以原不等式成立． 3.5 跳跃式数学归纳法 3.5.1这一变式的证法步骤是[3](184)P ：如果：（1）p(1),(2),,()p p m ⋅⋅⋅真；（2）()p k 真()p k m ⇒+真，那么()p n 对一切自然数n 真．3.5.2 例题解析例9 设01a <<．定义 11a a =+；11n na a a +=+ (1)n ≥ 证明；对一切n 有1n a >． 证明 （1）当1n =时，11a a =+>1命题成立．当2n =时，2221111111a a a a a a a a++=+==+>++， 命题成立． （2）假设n k =时，命题成立，1k a > 则221111111111k k k a a a a a a a a a a a ++++=+=+>+=>+++这就表明2n k =+时命题成立． 所以原命题成立．剖析 这一方法的主要证明思路是：当1,2,,n l =⋅⋅⋅时，这个命题都是成立的，并且证明了“假设当n k =时，这个命题正确，那么当n k l =+时这个命题也正确”于是当n 是任何自然数时，这个命题都是正确的． 3.6 翘翘板归纳法3.6.1 这一变式的方法是[4](34)P ：有两个命题,n n A B 如果“1A 是正确的”、“假设k A 是正确的，那么k B 也是正确的”、“假设k B 是正确的，那么1k A +也是正确的．”那么，对于任何自然数n ，命题,n n A B 都是正确的．3.6.2 例题解析 例10[4](34)P 在级数137121927374861+++++++++⋅⋅⋅里，如果n a 是它的第n 项，那么：223n a n =，213(1)1n a n n -=-+这里n 是大于或者等于1的整数．求证：2211(431)2n S n n n -=-+ 221(431)2n S n n n =++ 证明 令n A =2211(431)2n S n n n -=-+ n B =221(431)2n S n n n =++．显而易见1n =时． 11A =是正确的．假设2211(431)2k S k k k -=-+，那么222211(431)3(431)22k S k k k k k k k =-++=++ 这就是说，假设假设k A 是正确的，那k B 也是正确的．又假设221(431)2k S k k k =++，那么2211(431)3(1)12k S k k k k k +=+++++ 21(1)[4(1)3(1)1]2k k k =++-++因此对于任何自然数n ，命题,n n A B 都是正确的． 即原命题正确．3.7 超限归纳法这一变式是为了证明某些特殊命题的需要，将数学归纳法从正整数集推广至所有良序集而得到的．本文对这一变式只给出原理以便读者了解这种方法，就不再给出例题及证明了．超限归纳法原理：设(,)S ≤是一个良序集，()p x 是与元素x S ∈有关的一个命题：（1） 如果对于S 中的最小元0a ，0()p a 成立．（2） 假定对于任何x a <，()p x 成立，可证明()p a 也成立．则()p x 对于任何x S ∈都成立．4 数学归纳法的简单应用及证法技巧数学归纳法在数学上是很常用的方法，很多命题都可以用这种方法加以证明，请看下例： 例11 设{}n x 是由12x =，11(*)2n n nx x n N x +=+∈定义的数列．求证：1n x n<<成立． 分析由于112n n n x x x +=+>=n x >剩下的只要证1n x n<即可，考虑到其右边是一个与n 有关的代数式．故试用数学归纳法证之．证明 （1） 当1n =时，11x <，不等式成立．（2） 设(1)n k k =≥时，不等式成立，即1k x k<，那么，1n k =+时 由112k k k x x x +=+和归纳假设，知1k x k <，所以122k x k<+ ①111kx k>②，因①，②不为同向不等式，无法完成从k 到1k +的证明． 事实上，要证明1n k =+时命题成立，只有找到关系1kA x <才能推导下去，所以，寻觅出1k x A<中的A是此题的关键所在．如果我们注意到本题开头已证n x >了．k x >， 因为1k x <所以1111221k k k x x x k k +=+<<+ 即1k x +<11k +． 例12 已知n 个圆中每两个圆都相交于两点，且无三个圆过同一点，用数学归纳法证明：这n 个圆将平面分成22n n -+块区域．分析：用数学归纳法证明几何问题时，关键是要把n k =时和1n k =+时之间的关系弄清楚． 证明 （1）当1n =时，1个圆将平面分成2块区域，而22112=-+，所以命题正确． （2）假设n k =时命题正确，即满足条件的k 个圆将平面划分成22k k -+块区域．当1n k =+时，平面上增加了2k 个交点，而这2k 个点将1k +个圆分成2k 段弧，每块弧将原来的一块区域割成了两块区域，所以平面上增加2k 块区域，所以1k +圆将平面划分成222(2)22(1)(1)2k k k k k k k -++=++=+-++块区域．所以1n k =+时命题正确，由（1）（2），得命题对一切*n N ∈都正确．例13 设*n N ∈，用数学归纳法证明：23111112222n +++⋅⋅⋅+<． 证明 （1）当1n =时，不等式显然成立．（2）假设当n k =时不等式成立，即23111112222k +++⋅⋅⋅+< 那么，当1n k =+时，有231231111111111111()112222222222222k k k ++++⋅⋅⋅++=++++⋅⋅⋅+<+⨯= 这就是说，当1n k =+时不等式成立． 综合（1）（2）知原不等式成立．剖析 在将归纳假设“23111112222k +++⋅⋅⋅+<”作为条件证明， “23111111122222k k ++++⋅⋅⋅++<”时，应设法从2311111122222k k ++++⋅⋅⋅++中配凑出 2311112222k +++⋅⋅⋅+．但若按“23111111111222222k k k +++++⋅⋅⋅++<+”要其小于1则显然是不可能！至此，有的初学者会认为此题不能用数学归纳法，其实不然，只是配凑不恰当而已． 5 学好数学归纳法的几种方法5.1 学会从头看起在数学归纳法中，最原始而又不失去重要性的地方，便是从头做起．也就是1,2,3n =的 情形，向这些简单的情形讨教是最合算的，也是最可靠的．事实上，在很多问题上，如果真把这些最开头的几步看透了弄清了，想仔细了，那么解决的办法也就有了．在数学归纳法中更是如此．若失去了基础步骤也就是第一步，可能会得出荒谬的结论．所以说基础的也是最重要的． 5.2 在起点上下功夫起点的重要不仅仅表现在验证，而是其对后面归纳过度的启示．有时我们也会遇到一些问题，在其归纳的第一步上就很难，需要认真地下一番功夫，需要开阔思路，寻找合理的切入点．如：在第一步我们证明1n =成立．而第二步的证明中需要验证2n k =+这时我们的第一步就出问题了．第一步不仅要证1n =成立，还要证2n =时成立才能满足第二步的需要． 5.3 正确选择起点和跨度在数学归纳法的基本形式之下，第一步通常总是由验证0()p n 做起，这叫做“起步”， 0n 叫做“起点”，在通常情况下，起点一般只有一个．第二步则通常是由()p k 推出(1)p k +，或者说是由“n k =”跨到“1n k =+”，即每次跨一步．换句话说通常是以“跨度1”前进的，那么，这是不是说这种安排起点和跨度的方式一定不能改变的呢？显然不是的，人们可以根据问题的需要对起点和跨度作灵活而适当的安排．不过需要注意的是绝对不能造成逻辑上的漏洞．事实上，前面我们说到的跳跃式归纳法就是灵活而又恰当的安排了起点和跨度．5.4 选择适当的归纳假设形式在数学归纳法中，归纳假设总是以“假设当n k =时命题成立”的形式出现的．其实，这并不是归纳假设的唯一形式，前文我们所谈到的“有限项归纳法”和“第二数学归纳法”都是灵活地选取了归纳假设形式．5.5 非常规的归纳途径在数学归纳法的递推步骤中，无论是常规的一步一跨，由n k =到1n k =+；还是加大跨度数步一跨；甚至改变归纳假设形式，使得可由某个n k ≤跨至1n k =+；归纳中的进军路线都是一直-----WORD格式--可编辑--专业资料-----向前，只进不退的但有的时候，这种强硬方针导致一定的困难．这时，就应当采取较为灵活的态度，改变只进不退的进军路线，采用有进有退，进退结合的方式选取一条合适的归纳途径．这种方法就是我们前文说到的逆向归纳法，这种归纳途径往往是不甚规则的，在处理诸如此类的问题时，便要求我们在归纳途径的选择上持较为灵活的态度．5.6 合理选取归纳对象这种方法的运用上涉及的范围较广，只希望读者了解有这么一种方法而已．事实上，我们有时会遇到一些问题，其中的变量不止一个．甚至并不直接与自然数n有关，这时就要求我们对该问题合理的分析对归纳对象作出合理的安排与选择．总之，数学归纳法的应用比较广泛，方法也很多，可以讲凡是关系到自然数的结论都可以用它来验证．学习和应用数学归纳法能够培养学生的运算能力、观察能力、数学化能力、逻辑思维能力和解决综合问题能力．另外，数学归纳法也是初等数学与高等数学衔接的一个纽带．--完整版学习资料分享----。

数学归纳法原理(六种)：【第二归纳法】【跳跃归纳法】【反向归纳法】一行骨牌，如果都充分地靠近在一起（即留有适当间隔），那么只要推倒第一个，这一行骨牌都会倒塌；竖立的梯子，已知第一级属于可到达的范围，并且任何一级都能到达次一级，那么我们就可以确信能到达梯子的任何一级；一串鞭炮一经点燃，就会炸个不停，直到炸完为止；……，日常生活中这样的事例还多着呢！数学归纳法原理设P(n)是与自然数n有关的命题．若(I)命题P(1)成立；(Ⅱ)对所有的自然数k，若P(k)成立，推得P(k+1)也成立.由（I）、(Ⅱ)可知命题P(n)对一切自然数n成立．我们将在“最小数原理”一章中介绍它的证明，运用数学归纳法原理证题的方法，是中学数学中的一个重要的方法，它是一种递推的方法，它与归纳法有着本质的不同．由一系列有限的特殊事例得出一般结论的推理方法，通常叫做归纳法，用归纳法可以帮助我们从具体事例中发现一般规律，但是，仅根据一系列有限的特殊事例得出的一般结论的真假性还不能肯定，这就需要采用数学归纳法证明它的正确性．一个与自然数n有关的命题P(n)，常常可以用数学归纳法予以证明，证明的步骤为：(I)验证当n取第1个值no时，命题P(no)成立，这一步称为初始验证步．(Ⅱ)假设当n=k(k∈N，后≥no)时命题P(k)成立，由此推得命题P(k+1)成立．这一步称为归纳论证步．(Ⅲ)下结论，根据(I)、(Ⅱ)或由数学归纳法原理断定，对任何自然数(n≥no)命题 P(n)成立．这一步称为归纳断言步，为了运用好数学归纳法原理，下面从有关注意事项与技巧及运用递推思想解题等几个方面作点介绍．运用数学归纳法证题时应注意的事项与技巧三个步骤缺一不可第一步是递推的基础，第二步是递推的依据，第三步是递推的过程与结论．三步缺一不可．数学归纳法的其他几种形式还有：第二数学归纳法；跳跃数学归纳法；倒推数学归纳法（反向归纳法）；分段数学归纳法二元有限数学归纳法；双向数学归纳法；跷跷板数学归纳法；同步数学归纳法等。

第 11 讲 数学归纳法-证题原理及步骤（第1课时）数学归纳法⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧⎪⎩⎪⎨⎧⎪⎩⎪⎨⎧+==明探索性问题的猜想与证有关整除问题的证明等式或不等式证明数学归纳法的应用时命题成立推证时命题成立假设验证初始值数学归纳法证明的步骤推思想）数学归纳法的原理（递1k n k n n 重点：1．数学归纳法的原理与证题步骤；2．数学归纳法的应用。

难点：1．归纳、猜想、证明猜想；2．由k n =时的命题成立推证1+=k n 时的命题成立。

2．能进行一些探索性问题的归纳、猜想与证明,初步形成“观察→归纳→猜想→证明”的思维方法。

主要为证明不等式、恒等式以及整除这三个方面的应用，考题又常以数列问题为背景，将数学归纳法证与一些探索性问题综合起来考察。

⑴ 定义按下述步骤证明一个与自然数有关的数学命题的方法叫做数学归纳法： ① 验证当n 取第一个值时这个命题成立；② 假设当k n =，命题成立，然后证明当1+=k n ，命题也成立。

⑵ 数学归纳法与不完全归纳法的区别与联系 归纳是一种由特殊事例导出一般原理的思维方法。

归纳推理分完全归纳推理与不完全归纳推理两种。

不完全归纳推理只根据一类事物中的部分对象具有的共同性质，推断该类事物全体都具有的性质，这种推理方法，在数学推理论证中是不允许的。

完全归纳推理是在考察了一类事物的全部对象后归纳得出结论来。

数学归纳法是用来证明某些与自然数有关的数学命题的一种推理方法，在数学解题中有着广泛的应用。

它是一种递推的数学论证方法，论证的第一步是证明命题在n ＝1(或n 0)时成立，这是递推的基础；第二步是假设在n ＝k 时命题成立，再证明n ＝k ＋1时命题也成立，这是无限递推下去的理论依据，它判断命题的正确性能否由特殊推广到一般，实际上它使命题的正确性突破了有限，达到无限。

这两个步骤密切相关，缺一不可，完成了这两步，就可以断定“对任何自然数（或n ≥n 0且n ∈N ）结论都正确”。

浅谈数学归纳法的原理及应用姓名：王磊峰单位：砀山县豆集学区范套小学浅谈数学归纳法的原理及应用摘要：数学归纳法是证明与自然数有关命题的一种论证方法,也是数学证明中的一个强有力的工具，无论在初等数学还是高等数学中都有广泛的应用。

本文讨论了数学归纳法的理论依据、应用功能以及应用数学归纳法应注意的问题等。

关键词：数学归纳法；匹阿诺公理；应用；推理；命题；类型数学归纳法是数学中最基本也是最重要的证明方法之一，它在各个数学领域分支中都有极大的应用，因为使用面比较广，所以涉及的知识和技巧比较多，在本文中将介绍数学归纳法的产生、发展和确立并分别举例说明数学归纳法在各个方面的应用。

1数学归纳法的产生、发展和确立1.1数学归纳法的产生数学归纳法的产生经历了一个较长的历史时期，一般认为归纳推理可追溯公元六世纪的毕达哥拉斯时代。

这一时代杰出的数学家毕达哥拉斯利用点子数对级数求和问题进行了探讨，利用经过剖分后的正方形的直观形象，他确信无疑地得出：135+++ (2)-=，这里n n(21)有明显的推理过程，但这种推理只是简单枚举而没有碰到矛盾事实的归纳结果，因此是不完全的归纳推理，或者说只是一种寻求结论的手段，它只是作为一种猜想或假说，而不是可靠的，尽管如此，他仍为数学归纳法的产生奠定了一定的基础。

可靠的归纳推理是欧几里得对系数个数无穷的证明，虽然其中递推过程不甚明显，但基本思想却是按递推归纳原理指导的。

肯定地说，这一关于系数个数无穷的具体证明为后人对数学归纳法的认识提供了原形，促使人们加深了对数学归纳法的理解。

16世纪，经过文艺复兴洗礼的欧洲学者越来越意识到数学的重要性。

意大利数学家毛罗利科首先对全体自然数有关的命题的证明做了深入考察，他认为递归推理是指首先确定命题对于第一个自然数是真的，然后再去验证命题具有后继数也是真的。

于是，根据递推特性，命题对于第一个自然数的后继数为真，则对于第二个自然数也为真；对于第二个自然数为真，则对于第三个自然数也为真。

数学归纳法归纳法的发展历程数学归纳法是数学中一种重要的证明方法，也是中学数学一个非常重要的内容，用于证明与无穷的自数集相关的命题．但凡涉及无穷，总会花费数学家大量时间与精力，去理解并弄清它的真正意义．普通归纳法与自然数这一最古老的数学概念及“无穷”这个无法直观感觉的概念相结合的“数学归纳法”，自然也需要一个漫长的认识过程．有限个数字、元素、对象的认识很容易，因为它们很直观，一个个“数”或一个个“考察”即可，当数字、元素、对象多到无数个，即“无限”或“无穷”个时，就不是这么简单数数、看看的事了，因这无穷多的对象是无法完全“摆”出来直观感受的，如果再带上一些复杂的关系，那就更加无法直观反映了．在“无穷”多个对象时，较简单的情形就是与自然数相关的“无穷”，比如用{P (n)}表示与自然数n有关的无穷多的数字、元素、对象或性质、命题等．为了“数”清这无穷多的对象，或“看”清摆不出来的对象是否也带有看得到的对象所具有的复杂关系，那只能用“归纳”的办法去合理地“猜”，这就是普通“归纳法”的作用，是人类认识未知的一个普遍有效的方法，它是通过少数几个对象所显现的特征，根据后面对象与这少数对象在看得到、感觉得了的“相似”关系中，合理推测这些对象特征的办法．这时，也许你运气好恰好“猜”对了，也许没那么好的运气，一而再再而三地猜错，即使你猜对了，对数学家而言也不敢轻易恭维，因为他们需要的是“准确”的计数或“清晰”地看到性质，也就是说，必须对你的猜测给予严格的证明才能认可．如此一来，如何“准确”数、“清晰”看对象或其性质，就成了数学家伤脑筋的一个问题，这一“数”就数了两千多年．从普通不严密的“归纳法”发展到精确的“数学归纳法”，再到更一般的“超穷归纳法”、“连续归纳法”2.1.1 数学归纳法的起源追根溯源，数学归纳法可以在印度和古希腊时代的著作中找到丝缕痕迹，例如，印度婆什迦罗（Bhāskara，1114~约1185）的“循环方法”和欧几里得素数无限的证明中都可以找到这种踪迹．欧几里得《几何原本》第九卷命题20为：质数比任何指定数目都要多（注：质数也称为素数），即：素数无穷．欧几里得对这个命题的证法是经典的．他假定素数是有限的，不妨设这有限的n个素数为1p 、2p 、… 、n p ．然后作自然数1p ﹒2p …n p +1，并证明还存在新的素数，从而得到矛盾．因为若所作的数是素数，则它比全部给出的n 个素数都要大，因此是一个新的素数，这与假设有n 个素数矛盾；又若它不是素数，它必能被一素数整除，但它被已知全部的n 个素数1p 、2p 、… 、n p 除都有余数1，故整除1p ﹒2p …n p +1的素数必定是这n 个素数以外的新的素数，从而又与假设有n 个素数的条件矛盾．欧几里得素数无穷命题即是说，素数的个数与自然数的个数一样多．上述证明可以这样 翻译，首先，至少有一个素数存在，因为2就是素数，这一点在欧几里得的证明中没有指明；此外，上面欧几里得的证明表明，假如有n 个素数，那么就必定有1+n 个素数存在．也就是按现代数学归纳法的要求，证明了从n 到1+n 的递推关系，即完成了数学归纳法证明的关键性一步．但欧几里得没有使用任何明显的术语与现在的推理格式，因此，我们只能认为它蕴涵了现代数学归纳法的痕迹．2.1.2数学归纳法的发展直到十七世纪后，在数学归纳法有了明晰的框架后，各种形式的数学归纳法逐步得到发展，具体使用中的各种变异形式，如奠基步骤中的起始命题证明、归纳步骤中的跳跃台阶设置等都作了相应推广，发展出了最小数原理、第一和第二数学归纳法、反向归纳法、递减归纳法、螺旋归纳法、双重甚至多重归纳法等各种形式的数学归纳法．由于分析算术化的需要，数的理论也得到了充分发展，并最终将整个分析建基于自然数之上，至1889年意大利数学家C ·皮亚诺（C ·Peano ，1858~1932，意大利）发表 算术原理新方法，给出自然数的公里体系，不仅使全部微积分理论根基于此，也使数学归纳法有了一个准确、合理的理论基础．Peano 自然数公理系统：Ⅰ．1是一个自然数；Ⅱ．1不是任何其他自然数的后继；Ⅲ．每个自然数的后继是自然数；Ⅳ．若两个自然数的后继相等, 则这两个自然数也相等；Ⅴ． 若M 是由一些自然数所组成的集合，而且1属于 M ，且当任一自然数a属于M 时，a 的后继也属于M ，则 M 就包含了全部自然数．其中公理V 被称为归纳公理，是数学归纳法的逻辑基础．几乎同时，在分析算术化的过程中，对“无穷”概念作出了深刻的分析，扫除了微积分发展中的主要障碍，并对分析中的“不健康”点（不连续点、不收敛点等）逐渐有了深刻认识，为最终建立实分析奠定了基础．在对“例外”的考虑中，康托尔是独具慧眼的数学家，以此为起点，康托尔在 1897年建立了集合论基础，并对自然数作了深入、细致的研究，发明了超穷数，建立了超穷序数与超穷基数理论，并论述了良序集的特别理论，在此基础上将数学归纳法扩展为超穷归纳法．我们熟悉的归纳公理用集合论的语言可表述为：设S 是自然数集合N 的一个子集，如果：（1）1是 S 的元素；（2）从k 是S 的元素可推出k + 1是S 的元素. 那么，（3）S= N ．对于良序化的集合也有类似的性质：设 A 是良序化的集合，S 是 A 的一个子集，如果（1）A 的最小元素是 S 的元素；（2）x 是A 的元素，而从所有在A 中比x 小的元素是S 的元素可推出x 也是S 的元素. 那么，（3）S= A ．由彼此相似的良序集确定的数称为序数, 对于这样的良序集和序数相应的有下列超穷归纳法（有些教材或专业书直接将上述命题称为超穷归纳法）：超穷归纳法 设)(αΦ是序数α的一个命题，并且满足：如果任给β<α，)(βΦ都成立，则)(αΦ成立．那么，任给序数α，)(αΦ都成立．因为没有序数比0小，所以“任给β<α，)(βΦ都成立”总是真的，因此上述归纳法定理的条件中蕴涵着)0(Φ成立．应用时，有时需要特别证明)0(Φ成立．如若讨论的是大于等于某个序数0α的所有序数的性质，这时，与应用普通数学归纳法一样，需要对超穷归纳法条件需要稍加改动．上述条件改为：如果任给0αβ≤<α，)(βΦ都成立，则)(αΦ成立．易知，数学归纳法是超穷归纳法的特殊形式，但从数学归纳法不能推出超穷归纳法，因为自然数集只是特殊的良序集，而普通的数学归纳法无法跨越无穷达到“超穷”．数学归纳法和超限归纳法是对“离散”的无穷数集作出判断的严格的数学方法．对于连续情形，直到上世纪80年代才发现有一个十分简单而又便于掌握与应用的关于实数的归纳法，称为连续归纳原理或连续归纳法：设 P (x )为关于实数x 的一个命题，如果（i ）有某个实数0x ，使得对一切实数x <0x ，有 P (x )成立；（ii ）若对一切实数x <y 有 P (x )成立，则有y δ> 0，使 P (x )对一切实数x <y +y δ成立．那么，（iii ）对一切实数x 有P(x )成立．连续归纳法与数学归纳法或超穷归纳法形式极为相似，某种程度上表明离散的自然数集或良序集与连续的实数集在一定条件下的统一性．连续归纳法可以用来刻画实数系统的连续性公理，并推出一系列关于实数的命题，以及微积分中涉及连续的所有命题，连续归纳法的发现使有关实数的命题变得简单而易于掌握．至此，“归纳法”完成了较全面的、数学化的发展，“数学归纳法”在有限与无限之间架起了一座安全的桥梁．随着数学对象的进一步扩展，严格、准确的“归纳法”表达形式或许还会有更进一步的发展，因为数学概念的本身就是随着数学的整体发展以及人类认识的不断深化而逐步深入地修改、完善的，文献[8]用集合论的基本概念、现代数学的术语包括代数结构的语言与逻辑手段阐述数学归纳法，以表明数学归纳法的现代建构及其应用．综上所述，“归纳法”的精确化、成熟化几乎伴随了整个数学发展、成熟的历史, 从古代印度数学和古希腊欧几里得《几何原本》至二十世纪下半叶连续归纳法的发现．2.2 数学归纳法的原理分析2.2.1 数学归纳法的逻辑原理数学归纳法是一种证明与自然数n 有关的数学命题的重要方法．我们首先看一个简单的、人们熟悉的归纳集合，即自然数集N={0，1，…}．要确定N ，可先给出一个特殊的元素0，称为初始元，它是产生N 的基础．然后再给出一个由自然数产生自然的运算，即一元后继运算n ′（=n+1）．这个运算作用在初始元0上得到1，再作用在1上得到2，把这个过程一直继续下去，就可以依次把所有自然数产生出来．这个后继运算n ′有一个性质，即当n ∈N 时，则n ′∈N 。

概述数学上证明与自然数N有关的命题的一种特殊方法，它主要用来研究与正整数有关的数学问题，在高中数学中常用来证明等式成立和数列通项公式成立。

基本步骤（一）第一数学归纳法：一般地，证明一个与自然数n有关的命题P(n)，有如下步骤：（1）证明当n取第一个值n0时命题成立。

n0对于一般数列取值为0或1，但也有特殊情况；（2）假设当n=k（k≥n0，k为自然数）时命题成立，证明当n=k+1时命题也成立。

综合（1）（2），对一切自然数n（≥n0），命题P(n)都成立。

（二）第二数学归纳法：对于某个与自然数有关的命题P(n)，（1）验证n=n0时P(n)成立；（2）假设n0≤n<=k时P(n)成立，并在此基础上，推出P(k+1)成立。

综合（1）（2），对一切自然数n（≥n0），命题P(n)都成立。

（三）倒推归纳法（反向归纳法）：（1）验证对于无穷多个自然数n命题P(n)成立（无穷多个自然数可以是一个无穷数列中的数，如对于算术几何不等式的证明，可以是2^k，k≥1）；（2）假设P(k+1)（k≥n0）成立，并在此基础上，推出P(k)成立，综合（1）（2），对一切自然数n（≥n0），命题P(n)都成立；（四）螺旋式归纳法对两个与自然数有关的命题P(n)，Q(n)，（1）验证n=n0时P(n)成立；（2）假设P(k)（k>n0）成立，能推出Q(k)成立，假设 Q(k)成立，能推出 P(k+1)成立；综合（1）（2），对一切自然数n（≥n0），P(n)，Q(n)都成立。

应用（1）确定一个表达式在所有自然数范围内是成立的或者用于确定一个其他的形式在一个无穷序列是成立的。

（2）数理逻辑和计算机科学广义的形式的观点指出能被求出值的表达式是等价表达式。

（3）证明数列前n项和与通项公式的成立。

（4）证明和自然数有关的不等式。

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

下面介绍一些常见的数学归纳法变体。

从0以外的数字开始如果我们想证明的命题并不是针对全部自然数，而只是针对所有大于等于某个数字b的自然数，那么证明的步骤需要做如下修改：第一步，证明当n=b时命题成立。

第三节归纳原理和数学归纳法1．数学归纳法的理论依据归纳法和演绎法都是重要的数学方法．归纳法中的完全归纳法和演绎法都是逻辑方法；不完全归纳法是非逻辑方法，只适用于数学发现思维，不适用数学严格证明．数学归纳法既不是归纳法，也不是演绎法，是一种递归推理，其理论依据是下列佩亚诺公理Ⅰ—Ⅴ中的归纳公理：Ⅰ．存在一个自然数0∈N；Ⅱ．每个自然数a有一个后继元素a′，如果a′是a的后继元素，则a叫做a′的生成元素；Ⅲ．自然数0无生成元素；Ⅳ．如果a′=b′，则a=b；Ⅴ．(归纳公理)自然数集N的每个子集合M，如果M含有0，并且含有M内每个元素的后继元素，则M＝N自然数就是满足上述佩亚诺公理的集合N中的元素．关于自然数的所有性质都是这些公理的直接推论．由佩亚诺公理可知，0是自然数关于“后继”的起始元素，如果记0′＝1，1′=2，2′=3，…，n′=n＋1，…，则N=｛0，1，2，…，n，…｝由佩亚诺公理所定义的自然数与前面由集合所定义的自然数，在本质上是一致的．90年代以前的中学数学教材中，将自然数的起始元素视作1，则自然数集即为正整数集．现在已统一采取上面的记法，将0作为第一个自然数．定理1(最小数原理)自然数集N的任一非空子集A都有最小数．这本是自然数集N关于序关系∈(＜)为良序集的定义．现在用归纳公理来证明．证设M是不大于A中任何数的所有自然数的集合，即M=｛n｜n∈N且n≤m，对任意m∈A｝由于A非空，至少有一自然数a∈A，而 a＋1(＞a)不在M中．所然，就有1° 0∈M(0不大于任一自然数)；2°若m∈M，则m＋1∈M．根据归纳公理，应有M＝N．此与M≠N相矛盾．这个自然数m0就是集合A的最小数．因为对任何a∈A，都有m0意a∈A，于是m0＋1∈M，这又与m0的选取相矛盾．反之，利用最小数原理也可以证明归纳公理．因此，最小数原理与归纳公理是等价的．定理2(数学归纳法原理)一个与自然数相关的命题T(n)，如果1° T(n0)(n0≥0)为真；2°假设T(n)(n≥n0)为真，则可以推出T(n＋1)也为真．那么，对所有大于等于n0的自然数n，命题T(n)为真．证用反证法．若命题T(n)不是对所有自然数n为真，则M=｛m｜m∈N，m≥n0且T(m)不真｝非空．根据定理1，M中有最小数m0．由1°， m0＞n0，从而m0－1≥n0且T(m0-1)为真．由2°，取n=m0-1即知T(m0)为真．此与T(m0)不真相矛盾．从而证明了定理2．在具体运用数学归纳法进行数学证明时，有多种不同形式．运用定理2中两个步骤进行证明的，为Ⅰ型数学归纳法．经常使用的还有Ⅱ型数学归纳法，Ⅱ型数学归纳法是：如果命题T(n)满足1°对某一自然数n0≥0，T(n0)为真；2°假设对n0≤k≤n的k， T(k)为真，则可以推出 T(n＋1)也真．那么．对所有大于等于n0的自然数，命题T(n)都真．定理3Ⅰ型数学归纳法和Ⅱ型数学归纳法等价．证假设命题 T(n)对n=n0为真，于是只须证明“由T(n)(n≥n0)为真，可以推出T(n＋1)也为真”的充要条件为“由T(k)(n0≤k≤n)为真，可以推出T(n+1)也为真．”1°充分性若“由T(n)(n≥n0)为真，可以推出 T(n＋1)也为真”，则对n0≤k≤n，T(k)为真，特别 T(n)为真，因此 T(n＋1)也为真．2°必要性用反证法．若“由 T(k)(n0≤k≤n)为真，可以推出 T(n＋1)也为真”，但并非对所有大于等于n0的自然数n，由T(n)为真，可以推出 T(n＋1)也为真，则 M=｛m｜m∈N， m≥n0且由T(n)为真推不出T(n＋1)也为真｝非空．由定理1，M中有最小数m0，且对n0≤k＜m0的k，由T(k)为真，可以推出T(k＋1)也为真．特别由 T(n0)为真可知 T(n0+1)为真，由T(n0＋1)为真可知 T(n0＋2)为真，……，由T(m0－1)为真可知 T(m0)为真．现已知T(n0)为真，所以T(n0)， T(n0+1)，…， T(m0)都为真，由此可知 T(m0＋1)也为真，所以由 T(m0)为真推出了T(m0＋1)也为真．这与m0的选取矛盾．由定理3可知，Ⅱ型数学归纳法也是合理的推理方法．2．数学归纳法在应用中要注意的问题第一，证明的两个步骤缺一不可第一步是归纳的基础，第二步是归纳的传递．尤其是不可忽视第一步的验证．例1试证1＋3＋5＋…＋(2n＋1)＝(n＋1)2＋1证假设当n=k时公式成立，则1＋3＋5＋…＋(2n-1)＋(2n+1)＝［1＋3＋5＋…＋(2n-1)］＋(2n＋1)＝n2＋1＋2n＋1＝(n＋1)2＋1完成了数学归纳法的第二步，但结论显然是错误的．为什么？因为缺少第一步．事实上，当n=0时，公式不成立．如果缺了第二步，则不论对多少个自然数来验证命题T(n)的正确性，都不能肯定命题对所有自然数都正确．例如，哥德巴赫猜想“任何不小于6的偶数都可以表成两个奇素数之和”，虽然对大量偶数进行了具体验证，但因缺少第二步归纳传递，所以仍只停留在归纳的第一步上．它至今仍只是个猜想而已．第二，第二步在证明T(n＋1)为真时，一定要用到归纳假设，即要把“T(n)为真推出 T(n＋1)为真”或“T(n0)， T(n0＋1)，…，T(k-1)为真推出T(k)为真”的实质蕴含真正体现出来．否则不是数学归纳法证明．例2设a1，…，a n为n个正数，b1，…，b n是它的一个排列．试证证1°当n=1时，命题显然成立．2°假设(*)式对n=k成立，则当n=k＋1时根据数学归纳法原理，(*)式对所有大于等于1的自然数n都成立．这里虽然形式上完成了数学归纳法的两个步骤，但第二步在证(*)式对n＋1成立的过程中，并没用到(*)对n成立的归纳假设．因此，不能说上述证法是采用了数学归纳法．事实上，在上述证明中无须用数学归纳法，用平均值不等式证明就行了．第三，并不是凡与自然数相关的命题T(n)，都要用数学归纳法来证明；而且也不是所有这类命题都能用数学归纳法给以证明的．这一命题是与自然数相关的命题，尽管可以对n＝0，1，2，…进行验证，但无法实现数学归纳法的第二步，因此不能用数学归纳法进行证明．事实上，数学归纳法只适用于具有递归性的命题T(n)．3．递归函数一个定义在自然数集N上的函数f(n)，如果它对于每个自然数n的值可以用如下方式确定：(1)f(0)=a(a为已知数)；(2)存在递推关系组S，当已知/f(0)，f(1)，…，f(n-1)值以后，由S唯一地确定出f(n)的值：f(n)=S［f(0)，f(1)，…，f(n-1)］那么，就把这个函数f(n)，称作归纳定义的函数．简称递归函数．在具体的递归函数例子中，关系组S可能有几个表达式，或者没有明确的解析表达式，也可能需要给出f(n)的开头若干个值．这样定义函数是合理的，因为我们有：定理4 当递推关系组S给定后，定义在N上的满足上述条件(1)、(2)的函数f(n)是存在而且唯一的．证首先指出：对任一自然数k，总可以在片断｜0，k｜上定义一个函数f k(n)，使f k(0)=a，对于片断上其他自然数 n，f(n)=S［f(0)，…，f(n-1)］．这个函数f k(n)是在｜0，k｜上唯一确定的．现对k进行归纳证明：1°当k＝0时，f0(0)＝a是唯一确定的；2°假定在｜0，k｜上已经由(1)、(2)定义了一个唯一确定的函数f k(n)，令则f k+1(n)在片断｜0，k＋1｜上有定义，且(1)f k+1 (0)=f k(0)=a；(2)f k+1(n)=S［f k(0)，…，f k(n－1)］=S［f k+1(0)，…，f k+1(n－1)］，n=1，2，…，k．因此，函数人fk+1(n)满足条件(1)、(2)．由数学归纳法知，对任何自然数k，函数f k(n)在片断｜0，k｜上唯一确定，且满足(1)、(2)．又若k1＜k2，则 f k1(n)与f k2(n)在片断｜0，k1｜上完全一致．现作一新的函数：f(n)=f n(n)， n∈N．首先，函数f(n)对任一n∈N都有定义，且f(n)=f n(n)=S［f n－1(0)，…，f n-1(n－1)］=S［f0(0)，…，f n-1(n-1)］=S［f(0)，…，f(n-1)］又显然f(0)＝f0(0)=a．故函数f(n)是定义在N上且满足(1)、(2)的唯一确定的函数．例4设函数f∶N→N，且(1) f(0)=2，f(1)=3；(2) f(n＋1)＝3f(n)－2f(n－1)，n≥1．证明： f( n)＝2n＋1．这里给出的递归函数由f(0)、f(1)两个值和一个关系式给定的关系组S确定．但有的递归函数f(0)的值隐含于关系组S之中而未直接给出．例5(IMO－19试题)设f：N+→N＋，且(S) f(n＋1) ＞ f(f(n))， n∈N+求证：对于任意n∈N＋，f(n)＝n．证先用数学归纳法证明命题A n：任意正整数n，若m≥n，则f(m)≥ n．显然 A1真．假设A n-1真，则对任意m≥n，f(m－1)≥n-1，故f(m)＞f(f(m－1))≥2n－1，于是f(m)≥n，从而 An真．由此可知，f(n)≥n，f(n＋1)＞f(f(n))≥f(n)．于是f单调增加．又如果有一个n使f(n)＞n，则f(n)≥n+1，f(f(n))≥f(n+1)，与已知条件(S)矛盾．故只能有f(n)=n．本题给出的递归函数，f(1)的值没有明显给出，但实际上隐含于关系组(S)中．4．递归命题一个与自然数相关的命题T(n)，一般来说，它未必是一个函数问题．现在采取如下方式来构造命题T(n)的真值函数f∶N→｛1，0｝．如果命题T(n)的真值函数f(n)是递归函数，即1° f(0)=1；2° f(n＋1)= S［f(0)，…，f(n)］，且当f(0)=…=f(n)=1时， f( n＋1)=1．那么就称T(n)是具有递归性质的命题，或简称递归命题．实际上，所谓递归命题，就是一个与自然数相关的命题T(n)，开头(如n=0时)为真，且真值可传递并不是所有与自然数相关的命题都是递归命题．例如本节例3中的命题是与自然数相关的命题，而且对任何n∈N，它都为真，但却不具有递归性，它的真值是不可传递的．一般而言，大多数数论问题，如哥德巴赫猜想、费马问题、孪生素数问题等，都不是递归命题．只有递归命题才能用数学归纳法来证明．因此判别一个与自然数相关的命题T(n)是不是递归命题，是运用数学归纳法的前提．判别的关键在于，探究和发现T(n)的真值对于T(0)，…，T(n-1)真值的依赖性．而这种探究本身对于数学归纳法第二步证明，也有直接帮助．例6(1963年北京市竞赛题)2n(n∈N＋)个球分成若干堆，从中任选两堆：甲堆p 个球，乙堆q个球；若p≥q，则从甲堆取出q个加于乙堆；这作为一次挪动(变换)．证明：总可以经过有限次挪动，使所有球都归为一堆．这是一个与自然数相关的命题，记为T(n)．当n=1时，只有两个球，或已是一堆；或两堆，每堆一个球．若后者，只须挪动一次，就变为一堆．所以T(1)为真．T(n)真值是否有传递性呢？考察2n+1与2n，前者比后者多了一倍．如果设想每堆都是偶数个球，把每两个球用一个小袋装在一起，2n+1个球就变成了2n袋球．假设2n袋球都挪到一堆，那么2n+1个球也就挪到了一堆．这样就使T(n)的真值传递给了T(n＋1)．现在设法先将分球的情况变为每堆球数为偶数．假设不是每堆球数都是偶数，则球数为奇数的堆数一定为偶数(为什么？)．现将这2r堆奇数个球的堆两两配对，每对从较多的一堆向较少的一堆挪动一次．那么这2r堆每堆球数均为偶数(也可能出现空堆，如果一对中两堆球数相等的话)．这样便可以实施数学归纳法的第二步证明了．。