数学归纳法及其应用

    数学归纳法是一种证明与正整数有关的命题的非常重要的数学方法，它不仅对我们中学数学的学习有着很大的帮助,而且在进一步学习及研究高等数学时,也是一种非常重要的方法．数学归纳法在证明与正整数有关的命题时有其独特之处．对数学归纳法逻辑基础即原理的准确理解，是掌握这种证明方法的关键．要熟练的掌握及应用数学归纳法，首先必须准确的理解其意义以及熟练地掌握解题步骤，而在三个步骤中,运用归纳假设尤为关键,运用归纳假设推出结论最为重要．数学归纳法可以用来证明与正整数有关的代数恒等式、不等式、整除性问题和几何问题等．

  

正整数是无穷的．一个与正整数有关的命题，当时表示一个命题，当时又表示一个命题，如此等等，无穷无尽．因此，一个与正整数有关的命题本质上包含了无穷多个命题．假如我们对于这无穷多个命题，按部就班地一个一个去证，那么不管我们的证题速度有多快，也是今生今世都证不完的．

在一个与正整数有关的命题面前，作为万物之灵的人，发明了一种方法，叫做“数学归纳法”．人们运用此法，只需寥寥几步，像变戏法似的，便把无穷多个命题一个不剩的全证完了．

数学归纳法是数学论证的一个基本工具，是一种非常重要的数学证明方法，它典型地用于确定一个表达式在所有正整数范围内是成立的，或者用于确定一个其他的形式在一个无穷序列是成立的．最简单和最常见的数学归纳法证明是证明当属于所有正整数时一个表达式成立，这种方法是由下面两步组成，第一步是递推的基础: 证明当时表达式成立．第二步是递推的依据: 证明如果当时成立，那么当时同样成立．(递推的依据中的“如果”被定义为归纳假设． 不要把整个第二步称为归纳假设．) 这个方法的原理在于第一步证明起始值在表达式中是成立的，然后证明一个值到下一个值的证明过程是有效的．如果这两步都被证明了，那么任何一个值的证明都可以被包含在重复不断进行的过程中．

1     数学归纳法的概述

1．1  常用数学证明方法

数学是一门非常注重学习方法的学科,而数学的证明更是将这些方法体现的淋漓尽致，数学中研究问题的方法一般有以下分类：

1．1.1 演绎推理——从一般到特殊的推理叫做演绎推理，它又称演绎法．

1．1．2 归纳推理——由特殊事例得出一般结论的归纳推理方法，通常叫做归纳推理，它又称归纳法．根据推理过程中考察的对象是涉及事物的一部分还是全部，归纳法又可分为不完全归纳法和完全归纳法．

不完全归纳法是根据事物的部分（而不是全部）特例得出一般结论的推理方法．不完全归纳法所得到的命题并不一定成立，所以这种方法并不能作为一种论证方法．但是，不完全归纳法是研究数学的一把钥匙，是发现数学规律的一种重要手段．在问题探索中，为了寻求一般规律，往往先考察一些特例，通过对这些特例的不完全归纳形成猜想，然后再试图去证明或否定这种猜想．因而学会用不完全归纳法对问题进行探索，对提高数学能力十分重要．

完全归纳法是一种在研究了事物的所有（有限种）特殊情况后得出一般结论的推理方法，又叫做枚举法．与不完全归纳法不同，用完全归纳法得出的结论是可靠的．通常在事物包括的特殊情况数不多时，采用完全归纳法．

1.2  数学归纳法的定义

数学归纳法概念: 数学归纳法是数学上证明与正整数有关的命题的一种特殊方法，它主要用来研究与正整数有关的数学问题．

1.3  数学归纳法的逻辑基础

意大利有一个数学家，名叫皮亚诺（G．Peano,1858-1932），他总结了自然数的有关性质，并在关于自然数的理论中提出了关于自然数的五条公理，后人称之为“皮亚诺公理”．

皮亚诺公理的内容如下：

任何一个满足下列条件的非空集合的元素叫做自然数．在这个集合中，某些元素之间存在着一种基本关系——“随从”关系（或者叫做“直接后继”关系）并且满足以下五条公理：

Ⅰ．（即“0是自然数” ）．

Ⅱ． 对于的每一个元素,在中都有一个确定的随从（我们用符号表示的随从，以下类同）．

Ⅲ． 0不是中任何一个元素的随从．

Ⅳ． 由可以推出（这就是说，中的每个元素只能是某一个元素的随从，或者根本不是随从）．

Ⅴ． 设是自然数的集合，若它具有下列性质：

（1）自然数0属于；

 （2）如果自然数属于，那么它的随从也属于；

则集合包含一切自然数．

自然数就是满足上述皮亚诺公理的集合中的元素.关于自然数的所有性质都是这些公理的直接推论.由皮亚诺公理可知，0是自然数关于“后继”的起始元素，如果记，，，…，，…，则

皮亚诺公理与最小数原理是等价的，我们可以用皮亚诺公理来证明最小数原理.

定理1 （最小数原理） 自然数集的任意非空子集都有最小数.

证  设是不大于中任何数的所有自然数的集合，即

由于非空，至少有一自然数,而不在中，所以.从而必存在自然数，且.因为若不然，就有

（1）(0不大于任一自然数）；

（2）若，则.

根据归纳原理，集合包含一切自然数．此与是不大于中任何数的所有自然数的集合矛盾.

这个自然数就是集合的最小数，因为对任何，都有；而且.事实上，若，则有，对任意，于是，这又与的选取相矛盾.

下面我们用最小数原理来证明数学归纳法原理.

    定理2 （数学归纳法原理）一个与自然数有相关的命题，如果

（1）为真；

（2）假设为真，则可以推出也为真.那么，对所有大于等于的正整数，命题为真.

   证  用反证法.若命题不是对所有的自然数为真，则

非空.根据定理1，中有最小数.由（1），，从而且

为真.由（2），取即知为真.此与不真相矛盾.从而证明了定理2.

 因而从理论上讲，皮亚诺公理中的第五条公理正是数学归纳法的依据，因此，第五条公理也称做数学归纳法原理。

2  数学归纳法的步骤

数学归纳法的步骤相当严谨,如果把要证明的命题记作,那么数学归纳法的步骤为:

   （1）证明当取第一个允许值时，正确；

   （2）假设时，命题成立，即正确，证明当时，也正确．

   （3）根据（1）、（2），对任意正整数都成立．

运用数学归纳法证明时, 以上三个步骤缺一不可, 步骤（1）是正确的奠基步骤,称之为归纳基础, 步骤（2）反映了无限递推关系,即命题的正确性具有传递性,若只有步骤（1）, 而无步骤（2）,只是证明了命题在特殊情况下的正确性，是不完全归纳法,若只有步骤(2),而没有步骤（1）,那么假设成立,就是没有根据的,缺少递推的基础,也无法进行递推,有了步骤（1）和步骤（2），使递推成为了可能, （1）是整个数学归纳法证明的基础，（2）是最根本的一步，是整个数学归纳法证明的核心．通过（2），人们的认识才到达了质的飞跃——通过有限认识了无限．而作为纯形式的这一步骤，事实上相当于证明了一个新命题：“若真，则真”．步骤(3)是将步骤(1)与步骤(2)结合，完成数学归纳法中递推的全过程,因此三个步骤缺一不可．

数学归纳法的实质在于：将一个无法穷尽检验证明的命题转化为证明两个普通的命题：“真”和“若真，则真”，从而达到证明的目的．所以，可以说数学归纳法是“化归方法”的一种，它把“无限”的东西转化到“有限”上来．

3 数学归纳法的典型应用

数学归纳法是证明与正整数有关的命题的一种极为有效的方法，它在证明中的应用是十分广泛的．应用数学归纳法可以证明与正整数有关的恒等式、不等式、证明整除问题、证明几何问题等．

3．1证明恒等式

应用数学归纳法证明的恒等式，包括与正整数有关的代数恒等式、三角恒等式、组合数公式及其恒等式等，证明过程中只要实现等式左右两边相等即可．下面举例说明．

    例1  用数学归纳法证明：

    证明：(1)当时，左边，右边

         ∴左边=右边

(2)假设时，等式成立．即

      当时，

         

        ∴当时，等式也成立．

    由(1)(2)知，等式对任何都成立．

    例2   （2010江苏卷（理科））已知△ABC的三边长都是有理数．

        （1）求证：是有理数；

        （2）求证：对任意正整数，是有理数．

    证明：(1)由、、为有理数及余弦定理知是有理数．

    (2)用数学归纳法证明和都是有理数．

    ①当时，由（1）知是有理数，从而有也是有理数．

    ②假设当时，和都是有理数．

     当时，由

      ,

     

    由①和归纳假设，知与都是有理数．

    即当时，结论成立．

    综合①、②可知，对任意正整数，是有理数．

数学归纳法最简单的应用之一，是用来研究排列和组合的公式，通过高中的学习，我们已经知道：“从个不同的元素里，每次取个，按照一定的顺序摆成一排，称做从个元素里每次取出个元素的排列．”排列的种数，称做排列数．从个不同的元素里每次取个元素所有不同的排列数，可以用符号来表示．对于有下面的公式：

    定理1  

现在我们用数学归纳法来证明它．

证明：首先，．

这是显然的．如果再能证明

       ，

那么，这个定理就可以应用数学归纳法来证明．

我们假定个元素是在每次取出个元素的种排列法里，以为首的共有种，以为首的同样也有种，由此即得

         

    于是定理得证．

3．2 证明不等式

应用数学归纳法证明不等式，分为严格不等式和非严格不等式两种．严格不等式的证明，只要保证原不等式中的“﹥”或“﹤”成立即可．对于非严格不等式，情况略显复杂，在证明过程的第一步验证中，对于“”或“”的处理，存在两种不同的看法，一种观点认为：在第一步中，既要验证“”成立，也要说明成立．只有如此，才能更充分地体现非严格不等式成立．另一种观点认为：在第一步中，只要证明或有一个成立，即可说明非严格不等式成立．从逻辑连接词的角度，我倾向于后者．事实上，用数学归纳法证明非严格不等式时，是或的基础．

    例1 求证：

    证明：（1）当时，不等式成立．

   （2）假设当时命题成立，即

那么当 

      

  

    即当时，命题成立．

    根据（1）和（2），可知命题对任何都成立．

    例2 求证：

    证明：（1）当时，左边==右边

             ∴不等式成立

   （2）假设当时命题成立，即

    令

    那么当时，令

    则有

    ∴

    由归纳假设知，，则

    即当时，命题成立．

    根据（1）和（2），可知命题对任何都成立．

    有时候，我们要证明的不等式无法直接运用归纳法解决，这时，我们则考虑将不等式加强以便运用归纳法．而不等式加强的形式是多样的，其中规律有法可循——根据要证不等式的形式进行构造．

例3  已知数列满足

   （1）求的值；

   （2）设，求证：

   （3）求证：

    分析：（1）可以证明，于是

   （2）可用放缩法或数学归纳法证明．

现在考虑第（3）小题，尝试直接用数学归纳法证明，但由于不等式右边是常数2，很难利用归纳假设．

先考虑一个经典的问题：求证，我们可以使用放缩法证明，因此，我们可以使用数学归纳法先证明，，又因为有，从而证得，也就是我们可以将不等式进一步加强后再用数学归纳法证明．

鉴于此，我们重新考虑第（3）小题，把不等式加强成什么形式呢？

猜想，但发现当时不等式不成立，事实上，不等式是成立的，数学归纳法易证之．                         

3．3 证明整除问题

应用数学归纳法证明整除性问题，是数学归纳法的重要应用之一．在做这一部分题时，应从整除的基本含义入手，通过添项去项进行“配凑”，使之能够获证．

    例1  用数学归纳法证明：能被14整除.

证明：（1）当时，，能被14整除.

      ∴当时，命题成立.

   （2）假设时，命题成立.即能被14整除

    那么，当时，

           

         

        

     由归纳假设知能被14整除，又56能被14整除，故当时，命题也成立．

    根据（1）和（2），可知命题对任何都成立．

例2  用数学归纳法证明：能被整除（对于多项式，,如果,也是多项式，那么能被整除）

证明：（1）当时，，能被整除．

     （2）假设当时，能被整除，

那么当时，

        

    因为与都能被整除，所以上面的和

     

也能被整除．

    这就是说，当时，能被整除．

    根据（1）和（2），可知命题对任何都成立．

3.4  证明几何问题

    应用数学归纳法证明几何问题是数学归纳法的一个重要应用．数学归纳法是证明与正整数有关的命题的重要方法，但是运用它只能证明命题的正确性，而不能指望由它发现命题．数学家华罗庚曾在其《数学归纳法》一书中指出；“难处不在于有了公式去证明，而在于没有公式之前，怎样去找出公式来．”不少与正整数有关的几何问题，也可以用数学归纳法证明，但是在证明之前要找出规律，获得公式，然后才能用数学归纳法证明结论．

例1 平面内有条直线，其中任何两条不平行，任何三条不过同一点，证明交点个数等于．

证明：（1）当时，两条直线的交点只有1个，又

 ,

    因此，当时，命题成立．

   （2）假设时命题成立，就是说，平面内满足假设的任何条直线的交点的个数等于．现在来考虑平面内有条直线的情况．任取其中的1条直线，记为，由上面的假设，除以外的其它条直线的交点的个数等于．另外，因为已知任何两条直线不平行，所以必与平面内其他条直线都相交（有个交点）；又因为已知任何三条直线不过同一点，所以上面个交点两两不相同，且与平面内其他的个交点也两两不相同，从而平面内交点的个数是

                          

    这就是说，当时，条直线交点的个数

    根据（1）和（2），可知命题对任何大于1的正整数都成立．

    例2  求证凸边形的内角和．

    证明：（1）当时，

            ∵三角形内角和等于

            ∴当时，命题正确．

   （2）假设时命题成立，即

    当，连结边形有公共顶点的两条线段的两端点得到线段,则与除外的条线段组成一个边形，与组成一个三角形．

   ∴

   ∴当时，命题成立．

   由（1）、（2）可知，命题对都成立．

4  应用数学归纳法时容易出现的错误分析

刚刚接触数学归纳法时容易出现对步骤把握不清的现象，下面针对几种常见错误进行分析．

4.1    忽略了归纳奠定基础的必要性

   错例1 试证

   错证：假设时等式成立，即

     

   则当时，

           

    即当时等式成立．

    根据数学归纳法原理可知，当是任意正整数时，等式都成立．

评注：事实上，．因此错例1的题目是错误的．上述错证，竟把错误的结论“证明”出来了，岂非怪哉？此种怪现象出现的原因，就是缺少归纳奠定这一步．切莫以为归纳奠定这一步就是“当时命题正确”这么一句话，似乎无关紧要，可有可无．从上例可以看出，不去认真地检验这一步，或者根本没有这一步，就可能陷入错误的泥潭．因此，只有归纳递推、没有归纳奠定基础的论证是错误的．归纳奠基步骤决不能少．

4.2    弄不清从变化到命题发生变化时到底增加了几项

 例1  求证：

     当时，左边为

     则当时左边应为

就增加了括号中的那部分共项，而往往在此处由于受到前期思维定势的影响，判断为只增加一项，那就错了．

    又如前面3.2中的例2 求证：

    在解此题时，要注意弄清从变化到时，左边增加了几项．

在第二步假设时，即有

那么，当时，左边变化为

整体增加了一项，但尾项应比原来增加两项，即和 ．

4.3    在第二步证明中没有利用归纳假设

    比如用数学归纳法证明不少同学是按下列步骤展开的：

    证明：（1）当时，左边=，右边=2

∵左边右边

∴原不等式成立

（2）假设当时不等式成立，即，

那么当时，

   

          

 

 

∴时不等式也成立．

    由（1）、（2）知对于，命题成立．

    上述的证明方法表象似乎是“数学归纳法”，其实不是，因为第二步由推导时，没有用到归纳假设来证明不等式成立，这就好像接力赛跑一样没有由前一个将接力棒传给．

5 应用数学归纳法时的一些技巧

5.1 灵活选取“起点”

 第一步验证时，一般情况下也总能把命题证明出来，但对有些问题，则必须根据题目具体条件，对第一步做些调整，灵活选取起点，比如，适当的将起点前移或后挪，会对问题的解决大有帮助.所谓“起点的前移”是指对命题，若验证起点（如）比较困难或麻烦，而（如）有意义时，不妨将起点的验证移至；所谓“起点后挪”是指对命题，，，…，不能统一到“归纳”过程中去，这时可将起点后挪至，当然，，…，需要用完全归纳法予以一一验证.

例1  若、为正整数，则能被整除.

证明：（1）当时，显然成立.

（2）假设时命题成立.

    则当时，

                 

    由假设知，时命题成立.

    综合（1）、（2）知原命题成立.

   上例假设是为正整数，而我们第一步验证，这时命题显然成立，这比直接验证要容易的多.并且这样选择的“起点”并不影响后面的递推步，在这种情形下是允许这样做的.

例2  试证：对一切自然数，都有.

分析：不妨先看看第二步，

假设时，有，即.则当时，

.

∵,

由于，欲使上式大于0，必有，即.

这说明要完成归纳递推，必须从4开始.因而起点也必须从“后挪”至.此时第一步就应该是：

当时，（经验证）命题都成立.

这里运用了“起点后挪”的技巧.

5.2  恰当选取“跨度”

在归纳中，有时采用较大的跨度更为方便，就可以改变跨度，不过应注意随之而起点增多.

例1  试证：任意大于7的自然数均可表为若干个3与若干个5之和（若干个包括零个）.

证明：（1）当=8，9,10时，命题成立，由8=5+3,9=3+3+3,10=5+3知命题成立.

（2）假设时命题成立，则当时，只需再加一个3即可，显然成立.

综合（1）、（2）知原命题成立.上例递推跨度为3，起点验证也需要三个.

例2  求证对一切自然数，不定方程都有正整数解.

证明：当时，取；当，取，故知命题在和2时成立.

假设当时，，就有

，

知它们恰为方程的一组正整数解.所以当时，命题也成立.

则对一切自然数不定方程都有正整数解.

对上述两个例题，如果硬性规定跨度为1，则作茧自缚，而通过加大跳跃跨度，则大大降低了归纳难度.

5.3  选取合适的假设方式

同“起点”和“跨度”一样，归纳法的假设也可以是“因势而异”的，不一定非要拘泥于“假设当时命题成立”不可.事实上，“”往往可以用“”或“，”等等来代替.

5.3.1以“假设时成立”代替“假设时成立”

     例1  设数列{}满足关系式：

（1），

（2），试证数列的通项公式为.（加拿大数学竞赛试题）

分析  显然满足通项公式，但因

，

与，，…，都有关，如果仍设，就显得不够用了.按如果改设“对一切，都有”，问题即可解决，因为由

                

即可知也满足通项公式.

在上面的论证中，仅仅改变了假设的方式，而这种改变并未造成逻辑上的不合理，相反却有利归纳过渡，因而是十分可取的.

5.3.2以“假设，时成立”代替“假设时成立”

     有时也会碰到一些问题，它们的归纳需要依赖于前面两个命题同时成立，这时就应当用“假设，时成立”来代替通常的“假设时成立”，不过这样一来，起点也应增多为两个，否则，后面所作的假设就变得没有依据，整个论证也就变得不可信了.

例2  设与是方程的两个根，试证对任何自然数，都是整数，但不是5的倍数.

证明：为了便于使用归纳法，我们先来推导一下递推关系式.由韦达定理知：，因而就有

            

故知          ，

即有    .

    又当时，；当 时，

，故知当与2时，都是整数且不为5的倍数，现假设，时，也都是整数，于是由递推关系式

              

知当时，也是整数.所以对一切自然数，都是整数.

为证都不是5的倍数，以记其被5除所得的余数，于是由已证部分知，且由递推公式知.再证{}是一个循环数列，循环节是6.事实上，我们有

              

于是有               

从而知{}是以6作为循环节的循环数列.于是可以算出：

             

             

它们都不为0，这样我们就证明了对一切自然数，都不是5的倍数.

在本例论证的前一部分——是整数中，就采用了“与时，是整数”的假设形式，以便于利用递推公式顺利进行完成归纳过渡.这种假设形式，在论证数列问题时较为常用.但在使用时应注意对起点数作相应的增多.

5.4  改变归纳途径

若在由到的推导过程中陷入了困境，不妨先由退到，然后用归纳假设再回进到.这里的“退”是为了更好的“进”.

例1  设有个球分成了许多堆，可以任意选甲、乙两堆来按照以下规则挪动：若甲堆的球数不少于乙堆球的个数，则从甲堆拿个球放到乙堆去，这样算挪动一次，求证：可以经过有限次挪动将所有的球合并成一堆.

证明：当时，共有两个球，若已成一堆，则不必挪动；若分成两堆，则挪动一次即可.

假设时命题成立.对于个球，若将2个球“粘合”为1个便退到个球的情况，这种“粘合”要求每堆球的个数为偶数，为此，可分两种情况讨论如下：

（1）若每堆球的个数为偶数，则每挪动一次都挪动偶数个球，这样的任何一次挪动与将球两两“粘合”在一起挪动无本质区别，从而等价于个球的挪动，根据归纳假设，这是可以做到的.

（2）若存在球数是奇数的堆，则由总球数为偶数知，有奇数个球的堆数为偶数，将它们配对先挪动一次，于是每堆球数都为偶数，从而转为情况（1），问题得以解决.

5.5  主动加强命题

在归纳法的各种应用技巧中，最为有趣的要算是主动加强命题了，即为了归纳的需要，去证明一个比所要证明的命题还要加强的命题.乍一听，这似乎有点不可思议，但这正像“欲擒故纵”、“以屈求伸”一样，往往收到“殊途同归”之效.

例1  设，定义，（当），证明：对一切，有.

分析  显然有.但若仅设，则很难由递推公式推出，因为这里出现在分母上，为了得到，应当知道小于某个数值，而这一点恰恰是无法从由归纳假设中得到.为了克服这个困难，我们来证明：“对于一切，有

                  ”，

这当然是一个比“”还要强的命题，但证明起来却要容易的多：

首先由知及.假设，于是由递推公式知

，

，

这表明仍有

          ，

所以对一切，有都有.

6 数学归纳法的地位和作用

数学归纳法在讨论涉及正数无限性的问题时，是一种非常重要的数学方法，在数学的学习中，它的地位和作用可以从以下三个方面来看：

（1）中学数学中的许多重要结论，如等差数列、等比数列的通项公式及其前项和公式、二项公式定理等都可以用数学归纳法进行证明．对于由不完全归纳法得到的某些与正整数有关的数学命题，我们也常采用数学归纳法来证明它们的正确性．

（2）运用数学归纳法可以证明许多数学问题，如与正整数有关的恒等式、不等式、一些整除问题、一些几何问题等，既可以开阔眼界，又可以受到推理论证的训练．对于一些用常规的分析综合法不容易证明的题，用数学归纳法往往会得到一些意想不到的好结果．

（3）数学归纳法在进一步学习高等数学时会经常用到，因此掌握这种方法可以为今后的高等数学的学习打下一个良好的基础．

7  结 论

数学归纳法主要是针对一些与正整数相关的命题，所以在证明和正整数有关的命题时有着不可替代的作用，对于一些和正整数有关的长式子、繁式子都有化长为短、化繁为简的功效．用数学归纳法证明数学问题时，要注意它的三个步骤缺一不可，其中第一步是命题递推的基础，第二步是命题递推的依据，也是证明的关键和难点，第三步是将第一步和第二步结合，完成数学归纳法中递推的全过程。三个步骤各司其职，互相配合．同时，数学归纳法的证明步骤与格式的规范性是数学归纳法的特征，如时的假设是第二步要证明命题成立时一定要用到的，否则就不是数学归纳法．证明三角恒等式时，常常要用到有关三角知识、三角公式以及三角的变换法，通过这些变换可以更容易的让命题得证．在应用数学归纳法证明时，有许多技巧，如：灵活选取“起点”，恰当选取“跨度”，选取合适的假设方式，改变归纳途径，主动加强命题等.在证明时命题成立，也可用到一些技巧，如：凑假设，凑结论，加减项、拆项，不等式的放缩，等价转化等，这些解题的技巧要在实践中不断总结和积累，总之要记住三句话：“递推基础不可少，归纳假设要用到，结论写时莫忘掉”，这样我们才可以更好的运用数学归纳法．数学归纳法是一种重要的数学方法,也是中学数学的重难点之一,它在对于开阔眼界,训练推理能力等方面都有很大的帮助．