毕业论文 数学归纳法及其应用.pdf

郎惠玲摘要：本文主要从数学归纳法的基础、数学归纳法的原理、数学归纳法的类型、使用 数学归纳法的步骤、数学归纳法的应用等几方面进行阐述，介绍了数学归纳法在解决解行列 式问题、数列证明、不等式证明和数的整除证明等方面的应用，目的是通过应用数学归纳法 解题，从而培养运算能力、观察能力、逻辑思维能力和解决综合性问题的能力。关键词：数学归纳法；递推；不等式；整除数学归纳法是用来证明某些与自然数有关的数学命题尸仇）的一种推理方法，其基础是观察与实践.例如哥德巴赫猜想、二项展开式和笛卡尔-欧拉公式等，无一不是观察、实验和 归纳的结果.下面我从数学归纳法的基础、数学归纳法的原理、数学归纳法的类型、数学归纳法的应 用等几方面进行阐述.一、数学归纳法的基础严格意义上的数学归纳法产生于16世纪以后，意大利数学家莫罗利科首先对与自然数 有关的命题作了深入的考察.递归推理的思想方法是指：它首先确定命题对于第一个自然数是正确的，然后再证明命 题对于以后的自然数具有递推性，即如果一个命题对于第一个自然数是正确的，那么作为一 种逻辑必然，它对于该数的后继数也是正确的.意大利数学家皮亚诺（Peano,Giuseppe,1858-1932）于1889年在其著作算数原 理新方法中提出了著名的自然数公理体系，其中欧冠的“归纳公理”成为数学归纳法的理 论依据.皮亚诺自然公理的内容是：1是自然数；每一个确定的自然数Q,都有一个确定的后继数Q,也是自然数（一个数的后继数就是紧接在这个数后面的数，例如，1的后继数是2,2的后继数是3等等）；如果仄c都是自然数的后继数，那么8=1不是任何数的后继数；任意关于自然数的命题，如果证明了它对自然数1是对的，又假定它对自然数为真时，可以证明它对也真，那么，命题对所有自然数都真.（这条公理也叫归纳公理，保证了数学归纳法的正确性.）这条公理也叫归纳假设，即数学归纳原理.若将。也视作自然数，则公理中的1要换成0.二、数学归纳法的原理数学归纳法所根据的原理是正整数集的一个最基本的性质最小数原理.我们用N*表示全体非负整数的集合：N*=1,2,3,.1最小数原理：正整数集N*的任意一个非空子集S必含有一个最小数，也就是这样一个数QES,对于任意ce S都有定理1(数学归纳法原理)设有一个与正整数有关的命题.如果(i)当 时，命题成立；(ii)假设二人时命题成立，则/=左+1时命题也成立；那么这个命题对于一切正整 数都成立.证明：假设命题不是对于一切正整数都成立.令S表示使命题不成立的正整数所成的集 合.那么SW0.于是由最小数原理，S中有最小数鼠因为命题对于 成立，所以。W1.从而。-1是一个正整数.因为。是S中的最小数，所以0-S.这就是说，当 1时，命题成立.于是由(ii),当=。时命题也成立.因此。任S.矛盾.定理2(第二数学归纳法原理)设有一个与正整数有关的命题.如果i)当=k+1时命题成立；(ii)假设命题对于一切小于左的自然数来说成立，则命题对于人也成立；那么命题对于一切自然数来说都成立.证明：假设该命题不是对一切正整数都成立.令S W0是不成立的正整数构成的集合.力 是S中的最小数.因为命题对于=1成立，所以。W 1.从而命题对于一切小于。的自然数成 立.由(五)有=时命题也成立，因此ZzgS,导致矛盾.三、数学归纳法的类型1.完全归纳法完全归纳法是根据对某类事物的全体对象的考察，发现它们都具有某一种属性，从而得 出这类事物都具有这种属性的一般性结论的推理方法.完全归纳法又分为穷举归纳法和类分 法两种类型.穷举归纳法穷举归纳法是对具有有限个对象的某类事物进行研究时，将它的每个对象逐一进行考察.结果它们都具有某种属性，就得出这类事物都具有这种属性的一般性结论的归纳推理.例1.证明当MEN时，n 2,ke Z.N=3左+1 左N3）,这时要证明次+1=3根+5.因为 1=10 3x3,所以3左+10 3x3=3机+5，即3 左一3）+10=3加+5，取m=k 3,=2 就可以.N=3k ,这时要证次 1=3根+5.因为-1=6+5,所以 3左一1 二 3左一6+5=3根+5，取根=左一2,n-.综上结论，对任意正整数N 8,Nkg糖果都可以用3kg包装和5总包装不拆包组成.2.不完全归纳法不完全归纳法是根据对某类事物部分对象的考察而得出这类事物都具有这种属性的一 般性结论的推理方法.由于不完全归纳法的结论的判断范围超出了前提的判断范围，因而它 是一种或然推理（也就是似然推理），在数学中它又可以分为枚举归纳法与因果关系归纳法.枚举归纳法枚举归纳法是根据某类事物的个特殊对象，具有某种属性而作出的这类事物都具有这 种属性的一般性结论的推理方法.枚举归纳法虽然不能作为严格的论证方法，但它有助于发 现解题线索和提供研究方向.它的步骤可以概括为“实验一归纳一猜测”.例如，哥德巴赫猜想在最初就肯定是观察的结果，即如6=3+3,8=5+3,10=7+3,12=7+5,14=11+3,16=13+3,18=11+7,20=13+7,.进一步的实验使人们发现这一现象并不偶然，从而就提出了如下的猜想：“任何一个大 于4的偶数都可以表示成两个质数的和应当提及的是，这一猜想的正确性至今尚未得到证明.在几何中也可以找到很多在观察与实验的基础上进行归纳的例子.例如著名的“笛卡尔 一欧拉公式”也是利用此法得出的.即通过实际计算四面体、六面体、八面体、六棱锥、五棱柱及四棱台的定点数（V）、棱数（）、与面数（尸），可以得出如下表格：1E F V E F四面体464六棱锥7127六面体8126五棱柱10157八面体6128四棱台8126进而，通过对于表中的数据的仔细分析，就可以发现如下的关系式：V+F=E+2通过进一步的实验，我们又可发现这一关系式对任何一个（凸）多面体来说都是成立的.但是，由于枚举归纳法不是严格的论证方法，所以不免会出现错误的情况.例如大数学 家费马就犯过这样的错误：费马曾依据2喂+1=5,2”+1=17，2+1=257,22+1=65537都是质数的事实，提出了如下的猜想：“任何形如2*+1（其中为自然数）的数（称为费马数,记为工）都是质数但是到了 16世纪中叶，欧拉发现：第五个费马数F5 =225+1=4294967297）并不是质数，而是641与6700417的乘积.因果关系归纳法（科学归纳法）因果关系归纳法是指以某类事物的部分对象的因果关系作为前提，而得出一般性结论 的推理方法.例 3.设有%=sin 3,a2-sin 20,当 2 时（N）,ak-2cos 0ak_x ak_2,求通项an.1解：因为a3=2 cos sin 23-sin 2=sin 33+sin 2-sin 0-sin 33=2 cos 0 sin 33-sin 26=sin 40归纳猜想：an=sin nO.这个结果就是用因果关系归纳法得出来的.由于因果关系归纳体现了所研究的这类事物 的本质属性，因此一般来说，由因果关系归纳出来的结论要比由枚举归纳法得出的结论可靠 性大.四、使用数学归纳法的步骤下面我们通过例题来阐述利用数学归纳法解题的步骤并总结一些经验.n n+l*例4.证明等式1+2+3+二 ns N成立.2证明：当 时，左边等于1,右边等于1,左边等于右边，等式成立.假设当=左时等式成立，即k k+l 1+2+3+左2成立.则当=k+1时/、左（左+1 /、1+2+3+一+左+左+1 =-F 左+1 _（左+2 左+1 一 2 k+1（左+1 +1-2即当二左+1时命题成立综上所述，等式对任意孔eN*成立通过上述例题我们熟悉了用数学归纳法证明题目的过程，但是我们必须注意，不是所有 的与正数有关的命题都能用数学归纳法证明，必须注意逻辑关系的可推性.归纳奠基和归纳递推两者相辅相承，互为依存.归纳奠基验证当取第一个值时命题成立，验证了这一步就为递推打下了基础，是第二 步的假设依据.但是仅靠这一步还不能说明结论的普遍性，即使多验证几个数都是正确的，也不能保证对其他的数都正确，这就需要第二步递推.假设=左时命题成立，证明当=左+1时也成立，证明了这一步，就获得了递推的依据.1证明过程中的“成立”、“成立”、“也成立”、“都成立”的作用是不同的.第一个“成立”是在奠基过程中产生的，它说明验证过程对于取第一个数时命题是正确的，也就为归纳递推 奠定了基础.第二个“成立”是假设成立，是对递推逻辑关系进行的肯定，说明递推证明是 可以进行的从而由假设命题尸(左)推出命题尸化+1).“也成立”是对递推可以进行的证明，其中一个“也”字，说明了前后两个命题之间的逻辑关系和依存关系.“都成立”是在概括 归纳过程产生对比，是对前面三个成立”的继承，同时也是对前面的三个“成立”的肯定.因此由四个“成立”的依存关系就证明了所要证明的命题.由此可以看出，命题尸化)和命题尸(女+1)之间的逻辑关系和依存关系是数学归纳法的 灵魂.数学归纳法的证明过程是指上是证明前后两个命题的逻辑关系和依存关系的正确性.也可以说数学归纳法实质上是归纳推理和演绎推理的巧妙结合.五、应用数学归纳法时应注意的问题应用数学归纳法时，必须注意以下几点：第一，如何保证结论的正确性.所说的关于“稳定性(即能否由已研究过得特例“稳定 地过渡”到其他尚未研究过的特例)”的分析显然不能遗漏任何一个特例.因此，就数学归纳 法的应用而言，一个必要的条件就是：所考虑的对象应是“可排”的，也即可以按照自然数 的顺序予以编号.这样，只要按照这种编号顺序去研究结论的“稳定性”，就可保证不会遗漏 掉任何一个特例.第二，在实际的数学研究中，由于我们往往是通过特例的分析引出普遍结论的，因此主 要的问题就在于如何证明结论的“稳定性”.但是，如果就证明的全部过程而言，我们又必 须首先就某个特例检查结论的正确性.不然的话，我们就丧失了归纳的基础.另外，出于严格 性的考虑，我们又应对第一个对象进行检验，因为只有这样，才能保证我们的分析没有遗漏 掉任何一个特例.六、数学归纳法的应用1、数学归纳法证明整除性问题例5.求证：32n+2-8n-9(ne)能被64整除.证明：设冷=322加9i)当 时，/(1)=34 8 9=64,能被 64 整除.(ii)假设=左21时命题成立，即64 I 7的左)=32左+28左一9 二 3232%8左一17(*)那么，当=左+1时/(左+1)=/优+1)=32(+1)+2 8(左+1)9=3432-8-17(*)1将（*）转换为3 左）+8 左+17一 32带入（*）,有左+1 =32左）+64+1 因为64 I f k 64|64+1 所以64|32/左 +64仕+1 即当=女+1时命题也成立综上所述32n+2-8n-9（ne 能被64整除例6.求证62n+3n+2+3”e N*能被11整除.证明：设/（耳=62+32+3当几=1时，/1 =66,能被11整除；假设=左21时命题成立，即州的则当=k+1时/（左+1 =62左）11x3 无+3 11X31因为11|/,n（Hx3E_Hx3i 所以即当二人+1时，命题也成立综上所述，62n+3n+2+3n neN 能被H整除.2.数学归纳法在解行列式中的应用例7.计算下面的行列式：1(2述介);a00 00b0a0 0b000a b0000b a000b0 0a0b00 00a解：用数学归纳法证明：D2n(i)当=1时，有D2n=D2=a bQ?b a结论成立.(ii)假定当二左时结论成立，即D2k则当=左+1时，有2 伏+i)=(2(k+1)阶)a00 00b0a0 0b000a b0000b a000b0 0a0b00 00a按第1行=。(-1)展开i+ia0 0b00a b000b a00b0 0a000 00a(2左+1阶)+6(-1)2(2k+邛介)0a00b00a b000ba00b0 0ab00 001各彳二式（一讨.（一1 2（2左叫 按末行展开+可一1产叫+1/（一1 叫+1.七左=a2-b2）D2k,D2k结论成立.故对任何正整数，结论成立.3.数学归纳法证明不等式问题例8.证明：不等式1+丧+2j?N*证明：当=1时,假设当=上时,左边等于1,右边等于2,不等式成立;不等式成立.即1 1 1 71H产 H尸+,H-j=2、kV2 V3 4k那么，当扑=左+1时1 1 111+,H-=-4k VI+1H/=J-+1 1+1+1l k+上+左+1 +1 _ 2 左+1=2VI+1J左+1J/+1不等式成立综上所述，当eN*时1+11正十香+H0,其前71项和S=an+，求数列的通项公式.2 a解：由 0得0,且邑同理可得由此猜想下面用数学归纳法证明：当几=1时猜想成立；一 2-=Q+。2 S?A/22 1 S3=V3Sn=GS=Q H-=Q=21 ai J 假设当=左时&二 JI成立，则当二人+1时134+1=5/+1+-=-Sk+1-Sk+-ak+l 7 k+l k J整理得sg+1故1+i-y/k+1即=左+1时，猜想成立综上所述对任意EN*,S=G例11.尸数列是斐波那契(Fibonaci)在1202年提出的：假定一对大兔每月生一对一雌 一雄的小兔子，每对在两个月后也逐月生一对一雌一雄的小兔子，现设年初时在兔房里放一 对小兔子(刚出生的)，问一年后兔房里有多少对兔子？稍加分析后，便可得出兔子每月的对数的数列，即尸数列：1,1,2,3,5,8,13,21,34,55,89,尸数列的特征是从第三项起，后面每一项都是前面两项的和，即：%+i=%+%(心 2)(1)式属于线性递归数列，此数列的一般表达形式为：Pan+l+Qan+mn-l=0 式变形为。计1 一(+夕)&+S%=0 比较，式的系数得：p =a/3 I P由此可知。、夕是方程p%2+%+/=0(4)的根，此方程称为线性递归数列的特征方程，其根称为特征根尸数列的递推公式an+l=an+%T化为an+l-an-an-l=Q1其中p=l,q=r=l,它的特征方程为将 a,B 代入 an+i-(a+/3)an+a/3an_x且由于%=a2=1得1 y/-5 1+-/5 an+l+。J变形后，化为1+y/5 1-an+l 2 册=人 iVs,i+Vs令-一 2 贝应2晨%=41 V54=%2%所以4=1 yJ5 an+l=21 A/5 1 y/5=2 2 an-l+_ 2 十12 2-2 I 2 J-1二0(1-V5)(1+V5)n+22%=0向 1-V5)0 册)%l/).1，于是1+521 V5 1+5/5=1=2 2竽。+三卜+6小+灼I 2 J 口 2 J小一石甘+百广小+fl 2 八 2 J+2 JXfM2则所以6.利用数学归纳法证明几何问题例12.证明，当时，边形的内角和等于（孔2%.证明：这个命题对于=1,2来说是没有意义的.我们从=3开始用数学归纳法.当=3时，命题成立，因为三角形内角和等于4=（3-2）%.假设二左（左2 3）时命题成立.我们看任意一个人+1边形44+1 如图）.连 结AA，那么A4-A4+1的内角和等于三角形A4A的内角和再加上左边形 A&44+1的内角和前者等于乃，后者由归纳法假定，等于（左2%.因此上+1边形 A4 44+1的内角和等于%+（左+2%=（左1%=（左+1 2.命题得证.1例13.试研究个处于一般位置（既没有两个平面互相平行，也没有三个平面共线，或 四个平面共点）的平面把空间分割成多少个部分？这一问题是比较复杂的，为此我们不妨先来研究平面几何中与此类似的问题，即首先研 究条处于一般位置（既没有两条直线互相平行，也没有三条直线共点）的直线把平面分割 成多少个部分？对于后一问题，我们又可以采用“生成”的观点去进行研究，即具体地去研究当分割直线的数目九逐次增加时，分割所得出的部分平面的数目S,的变化情况.如图所示容易看出，在分割直线的数目由3增加到4时，分割所得的部分平面的数目的增加数也是4,而事实上也就是新增加的第四条直线乙被原有的三条直线分割所得的部分直线数，因为，每一个这样的部分直线都把原先的一个部分平面分割成了两个新的部分 平面.显然，依据后一分析，我们就不难引出一般的结论：现设在原有的（-1 条分割直线 的基础上又增加了一条新的分割直线（，由于这一直线/“被原有的（-1 条直线分成了 个部分直线（因为共有（几-1 个交点，如图），而每一个这样的部分直线又把原先的一个部 分平面分割成了两个新的部分.因此，就增加了个部分.这样，按照“生成”的考虑，条 处于一般位置的直线就把平面分割成了1n(n+1+1+2 H-n-F12个部分.在解决了上述问题以后，就可以进一步研究平面分割空间的问题.具体的说，通过类比容易想到：如果我们在原有的仇-1 个分割平面的基础上再增加 一个新的分割平面M,空间被分割所成的部分数匕的增加量就等于这一平面M被原有的 仇-1 个分割平面分割所成的部分平面数.由于没有两个平面是平行的，也没有三个平面是 共线的，或四个平面是共点的，因此这仇-1 个平面与分割成了仇一1)1)+1+二仆T)+22个部分.这也就是说，在增加了第个分割平面以后，分割所得出的部分空间的数量增加了n(n-l)+1个.2从而，依据“生成”的考虑，我们就可得出，个处于一般位置的平面把空间分割成了1+1+(2(2-1)、+1+I 2 J2 J-+11+2)2-+11+.+2 J=1+3(2、n n r-+12 2、乙 乙 7=1+5(12+22+-+n2 (1+2+-+72)+(1+1+,+1)1 n(n+l)(2n+l)1+1)=-2 6 2+n26n(n2+5=1+-6个部分.7.利用数学归纳法证明集合中的问题例14.证明，含有个元素的集合的一切子集的个数等于2.证明：设A为含有个元素的集合.当=1时，A的全部子集只有。和A,共有2=21个，命题成立.假设=左时命题成立，即A的一切子集共有2%个，则当二左+1时，取A中唯一 1元素记为那么A的一切子集分为包含8以外的元素有上个，设由它们构成的子集为4.显然，A的一切子集就是A的不包含6的一切子集，有于个；将匕与A的一切子集逐个作 并集，就得到A中包含6的一切子集，也有2%个，故A的一切子集总共有2%+2%=个,命题成立.8.利用数学归纳法证明二项式定理 例15.证明二项式定理：n 1 n=an+/+an+b：这里/、n+1)r是n个元素中取r个的组合数.证明：当=1时(Q+“a+b=a+a-lb命题成立；假设当二人时，命题成立，即/Ja+b?=ak+ak xb H-1-+/+r)于是=(+/?(+/7)I r(“+/?)vJak+1+1+C1kb H-FQT+/+1,左+1、(左+1、/、=尸+九+尸)-%+.”+1(1 J r?命题成立，故命题对一切正整数成立.9.利用数学归纳法证明最大公因式的问题例16.证明卜加1,x 1)=1的充要条件是(m,n)=d.证明：因为(jc),g3)=(g(x)J(x),所以不违一般性，可令心相，现对进1行归纳证明，当=加时，易见命题成立，若机时，命题成立，现需证(xm-l,xN-l)=xd-1的充要条件是(mN)=d.由初等变换知(xm-l,xN-l)=(xm-xN-l-xN-m(xm-l)=(xm-lxN-m-1)由归纳假设知(xm-xN-m-l)=xd-1的充要条件是(m,N _ m)=d利用求两个整数的最大公因数的方法可知(m,N m)=(m,N)=d命题得证.10.利用数学归纳法求个自然数的立方和问题例 17.求和 S=l3+23+33+-+n3.解：1=133+5=237+9+11=3313+15+17+19=43由此得出I3+23+33+-+n3=1+(3+5)+(7+9+11)+(13+15+17+19)+(-l)+l+zz(-1)+3+1)+2Tl 1L|2n(n+l)2其中第组中第一个奇数为n(n-l)/、2 +1-l=n(n-l)+l假设当二人时上述猜想成立，即12i3 Q3 13%（左+1 2则当二人+1时l3+23+-+Jt3+fc+l 3=+（左+1 3/7 2（左2+4左+1、二（左+i L I?k+1 左+2）一 2假设成立.故r2a a a +1 s=+23+.+/=-3L2可见，实践和归纳同样是数学家寻找真理和发现真理的主要手段.如多面体的面顶棱公 式、前个自然数的立方和公式、二项展开式等，无一不是观察、实验和归纳的结果.欧拉 说过“数学这门科学，同样需要观察、实验.”高斯也曾说过，他的许多定理都是靠归纳法 发现的，证明只是一个补行的手续.参考文献：口张禾瑞、郝金丙新：高等代数，高等教育出版社，1999年5月第4版.2 张雄、李得虎：数学方法论与解题研究，高等教育出版社，2003年8月第1版.3 郑毓信：数学方法论入门，浙江教育出版社，2006年3月第1版.4 吕孝亮：关于数学归纳法的基础研究，学术论坛，2008年12月号.1