数学归纳法的七种变式及其应用

1数学归纳法的七种变式及其应用1引言数学归纳法是数学中关于自然数命题的主要证明方法．学会并熟练运用这种方法，不仅可以帮助我们学习有关自然数的命题，而且还可以使我们更有力地解决相关问题．一般地说，与正整数有关的恒等式、不等式、数的整除性、数列的通项及前n项和等问题，都可以用数学归纳法解决．这种方法的难点在于由nk时成立，去证1nk时成立．很多情形下用常规的方法由nk成立时，去推1nk成立会走进死胡同，这时须另辟他径，完成证明．本文旨在通过对数学归纳法的主要七种变式加以剖析，以及一些证法技巧的介绍，使初学者提高对数学归纳法的认识和应用能力．2数学归纳法的原理和定义2.1数学归纳法的原理[1](36)P假定对一切自然数n，我们有一个命题，设为()Mn．如果下面两条成立：（1）(1)M是真命题；（2）对于任意的k，()Mk是真命题蕴含着(1)Mk是真命题，则对一切自然数n命题()Mn为真命题．2.2数学归纳法的定义当0nn时某命题正确，若在nk正确的情况下，能推出1nk也正确，便可递推下去．虽然我们没有对所有的自然数逐一的加以验证，但事实上这种递推就已经把所有自然数都验证了．这种方法就是数学归纳法．其步骤是：（1）验证当0nn时某命题正确（2）假设nk时，命题正确，从而推出当1nk时命题也正确．因此原命题正确．其中第一步是递推的基础，解决了特殊性；第二步是递推的依据，解决了从有限到无限的过度，这两步缺一不可，若只有第一步，则属于不完全归纳法；若只有第二步，则失去了假设的基础．对于1nk时的证明是整个数学归纳法的重点和难点．3数学归纳法的七种变式和应用3.1第一数学归纳法3.1.1这种方法是我们运用最多的，也是应用最广泛的一种方法．其步骤为[2](18)P：2（1）奠基步骤：证明当n取第一个允许值0n时，结论正确．注意0n不一定是1，也可能是其他的自然数．（2）递推步骤：假设当nk（0,kNkn）时结论正确，并以此来证明1nk时结论也正确．由步骤（1）、（2）得出结论：命题对于从0n开始的一切自然数均成立．3.1.2例题解析例1求证1111223(1)1nnnn（nN）证明（１）当1n时，111211这显然是成立的．（２）假设nk时命题正确；即：1111223(1)1kkkk则当1nk时，11111223(1)(1)(2)kkkk11(1)(2)kkkk(2)11(1)(2)2kkkkkk所以，对于所有的自然数n，等式都成立．例2求证111111234212nn111()122nNnnn证明（１）当1n时；左边11112211右边．（２）假设nk时等式成立，即：111111234212kk111122kkk当1nk时，左边1111111(1)2342122122kkkk11111()1222122kkkkk111112322122kkkkk=右边即1nk时等式成立．由（１）（２）得对于一切*nN等式成立．3例3设nN用数学归纳法证明：224621nnn证明假设当nk时等式成立，即224621kkk那么，当1nk时，有24622(1)kk212(1)kkk2(1)(1)1kk这就是说当1nk时等式成立．所以，nN时，224621nnn成立．剖析这是一种错证，缺少第一步．实际上当1n时等式不成立，题目本身是个错题．不要以为第一步“当1n时等式成立”无关紧要，可有可无，缺少第一步相当于失去了归纳基础，缺少第一步也会导出荒谬的结论，例如可以证出所有自然数都相等的结论．事实上，假定1kk成立，两边各加1就会得出：12kk由此可得出全体自然数相等！例4用数学归纳法证明：2nn1n(*)nN．证明（1）当1n时，21111，不等式成立．（2）假设当nk时不等式成立，即21kkk成立那么，当1nk时，22(1)(1)32kkkk2442(1)1kkkk这就是说，当1nk时成立．综合（1）（2）知原不等式对(*)nN成立．剖析这种证法是错误的，在数学归纳法的第二步中，在推证1nk时命题也成立的时候必须把归纳假设即nk时的命题作为条件用上，否则就不是数学归纳法了．正解（1）当1n时，21111不等式成立．（2）假设当nk时不等式成立，即21kkk，也就是22(1)kkk那么，当1nk时有，22(1)(1)()(22)kkkkk22(1)(22)43kkkk2442(1)1kkkk4就是说，当1nk时不等式也成立．综合（1）（2）知原不等式对nN成立．3.2第二数学归纳法3.2.1[2](58)P通过仔细学习数学归纳法原理，不难发现，如果将归纳假设改写成“假设当nk时，命题成立”，那里的证明仍可通过，这就启发我们在必要的时候，可以将归纳假设中的“nk”改写为“nk”事实上在很多问题的证明中，我们就是这么做的．这种假设形式的数学归纳法称作第二数学归纳法．3.2.2例题剖析例５[2](60)P证明每一个正整数都可以表示成互不相同的斐波那契数列之和．证明首先来看一下关于斐波那契数列，所谓的斐波那契数列是按照法则：12211,(1)nnnMMMMMn所定义的数列．当1n时，有11M知原命题成立．假设当nk时，命题成立，要证对1nk时命题成立，也就是要证明1k可以表示成不同的斐波那契数列之和．观察斐波那契数列可发现从3M开始斐波那契数列严格单调上升，故知存在m使：11mmMkM，如果1mkM则命题成立；如果1mkM，则有01mkMk由于1mkM是一个不超过k的自然数，所以由归纳假设知对其命题成立，即可将它表示成互不相同的斐波那契数列之和．又因为111mmmmkMMMM所以用以表示(1)mkM的斐波那契数均小于1mM，因此都不与mM相同，当将1k写成mM与这些数的和之后，即得到了1nk时的命题，可见对1nk，命题也成立，所以对一切自然数n命题都成立．在这里，由于我们是对(1)mkM使用归纳假设而(1)mkM并不一定就等于k，而是有可能小于k．所以若采用“nk”的归纳假设形式就会很麻烦了．例6已知对一切,0,nnNa且3211()nnjjjjaa，证明nan．证明当1n时由3211aa及0na，知11a，命题成立．假设当nk时，命题已成立，即有,1,2,,jajjk．要证，也有11kak，此时，一方面有：3333121kkaaaa23121()kkaaaa，另一方面有3333121kkaaaa2121()kkaaaa522121121()2()kkkkaaaaaaaa比较上述两式：即得：32111212()kkkkaaaaaa将121,2,,kaaak代入其中，得到32111(1)kkkakkaa又因为1ka0故由上式可得211(1)0kkaakk解此方程，得到11kak或1kak．由于10ka知1kak（舍）．因此：1kak+1从而知1nk时，命题也成立，所以对一切自然数都有nan．本题采用“nk”的假设，在通过方程求解1ka的过程中我们首先遇到的化简方程的问题，而这里面首先就是一个对12kaaa求和的问题，为了求出这个和数，离开了“命题已对nk全都成立”的假设，问题就不好解决了．3.3逆向数学归纳法3.3.1这种命题的表述为[3](185)P：如果：（1）对任一自然数n，总有0nn使0()pn真．（2）()pk真(1)pk真．那么，()pn对一切自然数n真．这种方法也可以形象地称为“留空回填”第一步证明了有无数个自然数nx使()npx真（1,2,3n）剩下的就是1,nnxx上的自然数尚未证明，再由第二步，有()npx真(1)npx真…1(1)npx真，这就把“空”填上了，所以这里的逆向倒推暗藏着正向推进的一面．3.3.2例题解析例7求证n个非负数的几何平均数不大于它们的算术平均数．证明分析n个非负数的几何平均数是112()nnaaa算术平均数是12naaan本题就是证明：11212()nnnaaaaaan（1）证明当1n是，（1）式显然是成立的，如果12,,,naaa里面有一个等于0，（1）式也是成立的．当2n时，（1）式是112212()2aaaa这可以由112212()0aa推出，现在我们来证明当2pn，p是任意自然数的时候，定理都是成立的．6假设当2kn的时候（1）式是成立的，那么1112122()kkaaa111122212221222[()()]kkkkkkaaaaaa11122122212221[()()]2kkkkkkaaaaaa1122212221[]222kkkkkkaaaaaa112212kkaaa所以当12kn的时候（1）式也成立．因此当2pn，p是任何自然数的时候（1）式都是成立的．进一步在推到一般的n，我们在假设当nk的时候（1）式成立的前提，下面来证明：当1nk时，它也成立．取1211kkaaaak，因为当nk的时候（1）式是成立的．所以1211kaaak121kkaaaak1121()kkkaaaa1121121[]1kkkaaaaaak两边同时除以1121[]1kkaaak得11121121[]()1kkkkkaaaaaak由此得11211121()1kkkaaaaaak即得所证．至此命题已得到了完全的证明．3.4有限项数学归纳法3.4.1这一证法的步骤是[3](183)P：设m为一给定的自然数如果：（1）(1)p真；（2）()pk真(1)km(1)pk真；那么()pn对不超过m的自然数n真．3.4.2例题解析例8已知,mnN且3nm求证：(1)mmmnn．7证明对m用数学归纳法．（1）当3m时，33332323326331(1)nnnnnnnnn命题成立．（2）设mkn命题成立．即(1)kkknn则1(1)(1)()()kkkkknknnknnknkn1(1)(1)(1)(1)kkknknnnn这表明1mk时命题成立．所以原不等式成立．3.5跳跃式数学归纳法3.5.1这一变式的证法步骤是[3](184)P：如果：（1）p(1),(2),,()ppm真；（2）()pk真()pkm真，那么()pn对一切自然数n真．3.5.2例题解析例9设01a．定义11aa；11nnaaa(1)n证明；对一切n有1na．证明（1）当1n时，11aa1命题成立．当2n时，2221111111aaaaaaaa，命题成立．（2）假设nk时，命题成立，1ka则221111111111kkkaa