浅谈数学归纳法及其应用.pdf

晋中学院 XX 学院 20XX 届本科生毕业论文浅谈数学归纳法及其应用学生姓名:XXX（XXX 班）指导老师:XXX摘 要:数学归纳法是数学中最基本也是最重要的证明方法之一,在数学各个分支里都有广泛应用,利用数学归纳法可以解决比较复杂的问题.本文从数学归纳法的整体结构出发,对数学归纳法的思想渊源、基本原理及常见形式进行了分析总结,介绍了数学归纳法在初等数学、高等数学、离散数学、概率论、图论等学科中的应用.关键词:数学归纳法;渊源;原理;表现形式;理论基础及其证明;应用 晋中学院 XX 学院 20XX 届本科生毕业论文On the Mathematical Induction and its ApplicationStudent:X XXInstructor:X XXAbstract:Mathematical induction is one way of the most basic and important mathematical proof,and has a wide application in several mathematics.Using the mathematical induction can solve the complicated problem.This paper begins from the overall structure of mathematical induction.Then mathematical induction on ideological origin,basic theory and common forms are analyzed and summarized.It is introduced by the application of mathematical induction in basic mathematics,discrete mathematics,probability theory,graph theory and other subjects.Key words:Mathematical induction;Origin;Theory;Manifestations;Theoretical foundation and its proof;Application 晋中学院 XX 学院 20XX 届本科生毕业论文目 录1 数学归纳法的思想渊源12 数学归纳法的原理23 数学归纳法3 3.1 数学归纳法的具体表现形式3 3.2 两种归纳法之间的关系44 数学归纳法的理论基础及其证明4 4.1 第一数学归纳法的理论基础及其证明4 4.2 第二数学归纳法的理论基础及其证明55 数学归纳法在各门学科中的简单应用6 5.1 数学归纳法在初等数学中的应用6 5.2 数学归纳法在高等代数中的应用8 5.3 数学归纳法在离散数学方面的应用 11 5.4 数学归纳法在高等数学中的应用 12 5.5 数学归纳法在图论中的应用 14 5.6 数学归纳法在概率论方面的应用 146 结束语15参考文献16 晋中学院 XX 学院 20XX 届本科生毕业论文01 数学归纳法思想的渊源追根溯源数学归纳法可以在印度和古希腊时代的著作中找到丝缕痕迹,例如,印度婆什迦罗（Bashkiria 1114约 1185）的“循环方法”和欧几里得素数无限的证明中都可以找到这种踪迹.欧几里得几何原本第九卷命题 20 为:质数比任何指定数目都要多（注:质数也称为素数）,即:素数无穷.欧几里得对这个命题的证法是经典的.他假定素数是有限的,不妨设这有限的 个素数为.然后作自然数nnppp,21并证明还存在新的素数,从而得到矛盾.因为若所作的数是素数,则它比121,nppp全部给出的 个素数都要大,因此是一个新的素数,这与假设有 个素数矛盾;又若它nn不是素数,它必能被一素数整除,但它被已知全部的 个素数.除都有余nnppp,21数 1,故整除的素数必定是这 个素数以外的新的素数,从而又与假设有121,npppn个素数的条件矛盾.n欧几里得素数无穷命题即是说,素数的个数与自然数的个数一样多.上述证明可以这样“翻译”,首先,至少有一个素数存在,因为 2 就是素数,这一点在欧几里得的证明中没有指明;此外,上面欧几里得的证明表明,假如有 个素数,那么就必定有n个素数存在.也就是按现代数学归纳法的要求,证明了从 到的递推关系,即1nn1n完成了数学归纳法证明的关键性一步.但欧几里得没有使用任何明显的术语与现在的推理格式,因此,我们只能认为它蕴涵了现代数学归纳法的痕迹.现代形式的数学归纳法被很多人认为是法国数学家、物理学家和哲学家帕斯卡(BPascal,16231662)发现的.例如,德国数学家和数学史家 MB康托尔(MBCantor,18291920)在他最重要的著数学史演讲卷 2 第 749 页中就这样误定,后来他在有关的杂志中作了纠正,他说,华卡(GVacca?)先生告诉我,意大利的莫洛里科斯(FMaurolycus,14941575,意大利的数学家、物理学家和工程师)在其1575 年出版的著作算术中描述并使用了数学归纳法.美国数学史家 H伊夫斯的数学史概论（第六版中译本）也认为帕斯卡 1665 年的论文三角阵算术中有数学归纳法的最早的、可被接受的陈述.其实,帕斯卡在给卡卡维(Carcavi 卒于 1684年)的一封信中已承认是莫洛里科斯引入了这一方法.近代最新研究表明,不仅帕斯卡不是数学归纳法的最早发明人,莫洛里科斯也不是最早使用这一方法的数学家,可被 晋中学院 XX 学院 20XX 届本科生毕业论文1接受的数学归纳法的使用年代比莫洛里科斯更早,十四世纪法国的数学家、天文学家和哲学家莱维本热尔松在其 1321 年出版的代表作计算技术中已经“本质上使用了数学归纳法”,更有资料表明,在中世纪伊斯兰数学中就已经较清楚、广泛(在多种著作中发现)地使用了数学归纳法的归纳推理.中世纪前期的欧洲被称为文化史的“黑暗时代”,文化教育名存实亡,古老学问濒临绝迹,技艺艺术逐渐遗忘,社会秩序严重被毁,暴力宗教肆意顺行.中世纪后期情况有所改观,十字军东征带回了东方文化,并从阿拉伯重新捡回了古希腊文化,此时欧洲数学自身的发展仍然及其缓慢,更多的是传播印度、伊斯兰等东方的数学知识,就连意大利数学家 L斐波那契(Lenardo F bonacci,约 11701250,也称比萨的莱昂那多),写于 1202 年的名作算盘书也主要介绍、引证了许多印度、伊斯兰等国的数学知识和数学问题,包括阿拉伯数字的写法、用法,四则运算、方程解法等,这本书作为教材在欧洲各国几乎使用了近 200 年,可见数学知识更新之缓慢.德国数学家和数学史家汉克尔(HHankel,18391873)风趣地形容这一现象,“人们惊奇地发现,莱昂那多给予欧洲的那一磅钱,在 300 年间竟丝毫没有生出什么利息”.JH伊夫斯则称,十四世纪欧洲相对地是数学上的不毛之地,这不仅因为十四世纪下半叶黑死病扫荡了欧洲三分之一以上的人口,也因为这是一个政治、经济动荡,战争不断的世纪,这种影响一直延续到文艺复兴.如此状况,莱维本热尔松的贡献也算是给中世纪欧洲数学增添了一份光彩.中世纪的伊斯兰则与欧洲大不相同,其商业繁荣,文化活跃,占希腊、印度的数学知识几乎全部传播到那里,被吸收消化并形成自己独特的风格,他们将希腊数学中几何证明的思想,转移到代数学研究中,希望能够证明代数规则的合理性.伊斯兰的代数中充满了证明的思想,很多计算问题都被他们扩展为可以对一般情形也成立的形式,归纳推理思想(这里的归纳推理指的是数学中的递推,而非普通逻辑中的归纳法的推理)就是在这样一种氛围中被逐步凝炼.2 数学归纳法的原理自然科学中的“经验归纳法”,是从某一现象的一系列特定的观察出发,归纳出支配该现象所有情况的一般规律,而数学归纳法则是迥然不同的另种手段,它用来证实有关无限序列（第一个,第二个,第三个,等等,没有一个情况例外）的数学定理的正确性.晋中学院 XX 学院 20XX 届本科生毕业论文2数学归纳法原理:假设我们希望证明一系列无限个数学命题,它们合1A2A3A在一起便构成一般的命题.如果Aa）通过某种数学论证可以证明,对于任一整数,如果命题已知为真,则命题rrA随之亦真;1rAb）第一个命题已知为真,那么序列中所有命题必都为真,从而得证.1AA数学归纳法的原理是奠基在下属事实的基础上:在任一整数 之后接着便有下一r个,从而从整数 1 出发,通过有限多次这种步骤,便能达到任意选定的整数.1rn推广后的数学归纳法原理:假设给定一系列命题,其中 是某正sA1sA2sAs整数,如果a）对于每个,的正确性可以从的正确性导出,sr 1rArAb）已知为真 sA则所有命题,均为真;换句话说,对于所有的,为真.sA1sA2sAsn nA我们再次强调指出,在自然科学中,数学归纳法原理与经验归纳法是完全不同的,一般的定律如果被证实了任意有限次,那么不论次数多么多,甚至至今尚未发现例外,都不能说该定律在严格的数学意义下被证明了,这种定律只能算作十分合理的假设,它容易为未来的经验结果所修正.在数学中,一条定律或一个定理所谓被证明了,指它是从若干作为真理接受的假设出发而得到的逻辑推论.人们考察一个定理,如果它在许多实例中是正确的,那么就可猜想定理在普遍意义下将是真的;然后人们尝试用数学归纳法以证明之.如果尝试成功,定理被证明为真;如果尝试失败,则定理的真伪未定,有待以后用其他方法予以证明或者推翻.因此在应用数学归纳法原理是要牢记 a）和 b）必须真正的满足.3 数学归纳法3.1 数学归纳法的具体表现形式归纳法分为完全归纳法和不完全归纳法,而数学归纳法属于完全归纳法,它又分为有限数学归纳法和超限数学归纳法,前者有两种不同的形式,它们分别叙述为:第一数学归纳法:如果性质在时成立,而且在假设了时性质)(nP1nkn 晋中学院 XX 学院 20XX 届本科生毕业论文3成立后,可以推出在时性质也成立,那么我们可以断定性质)(kP1 kn)1(kP对一切自然数都成立.)(nPn第二数学归纳法:如果性质在时成立,而且在假设了对所有小于或等于)(nP1n的自然数性质都成立后,可以推出在时性质也成立,那么性kn)(nP1 kn)1(kP质对一切自然数都成立.)(nPn与第一数学归纳法相比,第二数学归纳法把它的归纳假设加强了.3.2 两种归纳法之间的关系定理 3.2.1 第一数学归纳法和第二数学归纳法等价.证明 假设性质在时成立,于是化为证明:“由成立,则可以推出)(nP1n)(kP成立”的充分必要条件为“由（其中）成立,可以推出成)1(kP)(nPkn)1(kP立”.必要性:由已知“由成立,则可以推出成立”,假设时成)(kP)1(kPkn)(nP立,特别成立,所以成立.得证.)(kP)1(kP充分性:（反证法证明）由已知时成立,可以推出成立,对“由kn)(nP)1(kP成立,则可以推出成立”取反，于是,由成立推不出成立)(kP)1(kP)(0kP)1(0kP的所有自然数构成一非空子集,记为该子集的最小自然数.所以,对任一自然数,只0mn要,那么由成立可以推出成立.特别,由成立可知成立,由mn)(nP)1(kP)1(P)2(P成立可知.已知成立,因此、都成立,然而由)1(mP)(mP)1(P)1(P)2(P)(mP此可知成立,所以从成立推出了成立;另一方面,由的选取可)1(mP)(mP)1(mPm知,由成立推不出成立,这就导出矛盾,得证.)(mP)1(mP4 数学归纳法的理论基础及其证明4.1 第一数学归纳法的理论基础及证明第一数学归纳法的理论基础为自然数的序数理论,是由意大利数学家 Peano 于1889 年在他的著作 算数原理新方法 中提出.理论用公理化的方法从顺序的角 晋中学院 XX 学院 20XX 届本科生毕业论文4度揭示了自然数的意义,即我们所说的自然数 1、2、3理解为第 1 个、第 2 个、第 3 个下面用定义的方式给出这个公理的内容.定义4.1.1 一个非空集合的元素叫做自然数,如果的元素之间有一个基本NN关系“后继”(用符号来表示),并满足下列公理:(1),对,N1N1 (2)对任何有唯一的后继元素 N(3)以外的任何元素只能是一个元素的后继元素,即 不排在任何自然数后面11(4)归纳公理:若且 NM M1 则(自然数集)MMNM N定义中的一组公理叫 Peano 公理.它完整地刻画了自然数列.而其中的公理(4)即归纳公理可推出第一数学归纳法.第一数学归纳法:设是一个与自然数有关的命题,如果:成立,假设)(nP)1(P成立,则成立,那么对任意自然数都成立.)(kP)1(kP)(nP证明 设是由满足的自然数组成的集合则M)(nPNM 成立,则)1(PM1又假设成立,则成立)(kP)1(kP即,即.由归纳公理,为自然数集,MkMk1MkMk NM M即对任意自然数都成立.)(nP从上述证明过程可以看出第一数学归纳法的理论依据为归纳公理.4.2 第二数学归纳法的理论基础及证明第二数学归纳法也属于数学归纳法.它的理论依据为最小数原理,而最小数原理实际上也是归纳公理得出的.最小数原理:自然数集的任一非空子集中必有一个最小数.证明 设为的任一非空子集,假设且,则必为某一自然数的ANNn1nnm后继.晋中学院 XX 学院 20XX 届本科生毕业论文511mmn自然数集有最小数N1 当,有最小数A1A1当时,假设没有最小数,构造集合|且对,则A1ATxNxAaax.T1假设,若,则为中的最小数,与假设矛盾.TnAn11nATn1那么,时T1TnTn1由归纳公理则与为非空集矛盾NT AA的任一非空子集中必有一个最小数.N以上是用归纳公理对最小数原理作证明.下面用最小数原理对第二数学归纳法做一个证明.第二数学归纳法:设是一个与自然数有关的命题,若下列两个条件成立)(nP成立)1(P假设对于所有满足成立,则成立)(nPkl)(kP那么对所有自然数成立)(nP证明 设为满足成立的所有自然数的集合,设,假设,M)(nPnMNTT根据最小数原理有最小数.由条件成立,则.T0t)1(PM110t、12Mt10又由条件矛盾Tt 0TNM 对任意自然数成立.得证.)(nP 晋中学院 XX 学院 20XX 届本科生毕业论文65 数学归纳法在各门学科中的简单应用5.1 数学归纳法在初等数学中的应用数学归纳法在归纳猜想问题及不等式证明问题中等都有着广泛的应用.例 1 对任意自然数,求的和.n141351151312n证明 设141351151312n的和为,nS则=.nS141351151312n1411341124111412222n先对分别进行计算,再寻找其中的规律.5,4,3,2,1n显然.115,94,73,52,3154321SSSSS的下标就是项数,观察,可以看出他们的分子都与其项数相同.把分母变形,S51 SS则有.655,544,433,322,21154321SSSSS或者再写成.1525,1424,1323,1222,112154321SSSSS于是我们就猜想:.再观察n=6 的情形,有,又符合12 nnSn16261366S我们的猜想.再观察一下n=7,则有.此时我们对于上面的猜想就更17271577S有信心了.然而至今采用的还是经验归纳法,要确定是的求和公式,还要经过严格12 nnnS的证明.如何证明它呢?这恰好是一个与自然数有关的命题,所以我们不妨试一下数学归纳法.设 晋中学院 XX 学院 20XX 届本科生毕业论文712 nnSn只要能证得3211)1(211nnnnSn即可.事实上321)32)(12()1)(12()32)(12(1)32)(12()32()122)(122(1121)1(21121)1(412221nnnnnnnnnnnnnnnnnnnnSSnn证毕.5.2 数学归纳法在高等代数中的应用数学归纳法在高等代数中的应用也很突出,这主要是由高等代数内容体系所决定,其中许多证明及行列式的计算等,都要用到数学归纳法.例 2 设aaaaaaaaaA2121212122222是阶矩阵,证明行列式n.nanA)1(证明 记,nnnaaaaaaaaaAD2121212122222下面用数学归纳法证明:晋中学院 XX 学院 20XX 届本科生毕业论文8当时,命题正确.1naD21nnanD)1(当时,命题正确.2n2223212aaaaDnnanD)1(当时,命题正确,对按第一列展开得kn nnanD)1(kD1222122122222121201)1(2121212122kkkaaaaaaaaaaaaaaaaaD2212kkDaaD按归纳假设,11kkkaD22)1(kkakD从而,kkkkakakakaaD)1()1()(2221所以,命题正确.nnanA)1(例 3 计算行列式:nnnnnnnnD)1cos()1cos()1cos()1cos(2cos2cos2cos2coscoscoscoscos1111321321321分析 这个行列式如果直接计算很困难,也很难发现什么规律.但是,如果先从特殊情况入手就容易发现规律.当时,3n1cos21cos21cos2coscoscos1112cos2cos2coscoscoscos1113222123213213213D 晋中学院 XX 学院 20XX 届本科生毕业论文9322212321322212321coscoscoscoscoscos1112cos2cos2cos2coscoscos11131)cos(cos2jiij这里利用了范德蒙行列式的计算公式.当时,4n43214321432143cos3cos3cos3cos2cos2cos2cos2coscoscoscoscos1111D443333223113423222124321cos3cos4cos3cos4cos3cos4cos3cos41cos21cos21cos21cos2coscoscoscos111143332313423222124321cos4cos4cos4cos4cos2cos2cos2cos2coscoscoscos11114121)cos(cos2jiij由此可以猜想:njiijnnnjiijnnD12)1)(2(1)2(321)cos(cos2)cos(cos2下面用数学归纳法证明.证明 当时,已证,原等式成立.3n假设时,原不等式成立,下证时也成立.)3(3kkn1 kn132113211321coscoscoscos2cos2cos2cos2coscoscoscoscos1111kkknkkkkD 晋中学院 XX 学院 20XX 届本科生毕业论文10将行列式的第行加到第行,再将第行的加到第行.然后将第1k1kk1cos21k行加到第行,将第行的加到第行,依此类推2kk1k1cos2k)cos(cos)1cos(20)cos(coscos20coscos011122122121kDk)cos(cos)1cos(2)cos(coscos2coscos111111111kkkkkk11113122)cos(cos)cos)(coscos(coskk22)1cos(cos1k ,1212)1cos()1cos(coscos11kkkk由假设得:132132)1cos()1cos()1cos(coscoscos111kkkkk122)1)(2()cos(cos2kjiijkk从而有:122)1)(2(11113121)cos(cos22)cos(cos)cos)(coscos(coskjiijkkkkkD112)1()cos(cos2kjiijkk所以猜想成立.晋中学院 XX 学院 20XX 届本科生毕业论文115.3 数学归纳法在离散数学方面的应用离散数学以离散问题为研究对象其中很多的结论均与自然数有关,并可以运用数学归纳法来证明离散数学中的某些结论,如有关集合中关系及性质、树及其性质等,这样既降低了证明过程的复杂性,又使推理过程更加严密清晰.例 4 已知设,是个正整数,已知,证明存在结1d2dndn2n221ndnii点度数分别为,的一棵树.1d2dnd证明 对结点归纳证明,可构造满足条件的树.nT(1)时,由,而,所以,于是存在为2n22421 dd1d2d1121 dd2T满足条件的树.(2)假设时结论成立,即存在结点度数分别为,的一棵树,要kn 1d2dkd1T证时,结论也成立.1 kn由,均为正整数,知这个数中至1d2dkd1kdkkdkii22)1(2111k少有二个为 1,否则,与条件矛盾.1211kdkii不妨设,于是,这样,中至少有一个大于等于 2,11kd121kdkii1d2dkd否则矛盾.kdkii1不妨设,于是,2kd11kd221)1(111kdddkiikkii考虑,这个正整数,由归纳假设知,存在结点度数分别是,1d2d1kd1kd1d,的一棵树,在中从度为的结点引出一条边,另一端点2d1kd1kd1TT1kdkv记为,这样得一棵新树,在中,.1kvTTkkdv)deg(1)deg(11kkdv于是,因此,即为所求的一棵树.2)1(2)deg(111kdvkikiiiT5.4 数学归纳法在高等数学中的应用 晋中学院 XX 学院 20XX 届本科生毕业论文12例 5 证明不等式.)(2131211NnnnL证明 (1)当时,左边,右边,左边右边.1n12不等式成立.(2)假设当时,不等式成立,即kn,kkL2131211当时,则1 knkkkkL11211131211(现在关键证明)12112kkk 012121211)1(12111212112kkkkkkkkkkkkk,即当时,原不等式成立.12112kkk1 kn综合(1)(2)对于任意自然数命题成立.n例 6 求证)0(sinsin22sin2cos2cos2coscos12aaaaaLaannn证明 (1)当时,左边1n,aaaaaacossin2cossin2sin22sin所以当时命题成立.1n(2)假设当时命题成立,即:)1(kknaaaaLaakkksin22sin2cos2cos2coscos12将此试的两边同乘以得:ak2cos 晋中学院 XX 学院 20XX 届本科生毕业论文13aaaaaaLaakkkkk2cossin22sin2cos2cos2cos2coscos12aaaaakkkkksin22sinsin222cos2sin211所以当时命题成立.综合(1)(2)对于任意自然数命题成立.1 knn5.5 数学归纳法在图论中的应用例 7 大于 7 公斤整公斤的重量都可以仅用一些 3 公斤和 5 公斤两种砝码来称量.证明 只需证明对任意的自然数,存在二分图,其顶子集有个顶点,每8n nGXn顶皆一次,顶子集中的顶是 3 次或 5 次的.Y下面用数学归纳法证明之.当时,结论显然成立,见下图:8n1x2x3x5x8x7x6x4x2y1yXY 假设对于,结论一成立,.以下证明对,结论仍成立.为此,在 kG8k1kG的顶子集中添加一项;由归纳法假设,在的中顶是 3 次或 5 次的,分 kGX1kx kGY以下情形讨论:(i)若中皆 3 次项,取,将其重合成一项,再于与之间连Y1y2y3y123y123y1kx一条边,最后把劈开成两个 5 次项,则得满足要求的.123y1kG 晋中学院 XX 学院 20XX 届本科生毕业论文14(ii)若中有 5 次项,设,在与之间连一边,再把劈开成两个 3Y5)(iydiy1kxiy次项,则得满足要求的二分图.1kG证毕.5.6 数学归纳法在概率论方面的应用在概率问题中常会遇到一些与实验次数无关的重要结论,这些结论在使用数学归纳法来证明时,常常需要配合使用全概率公式,从而使概率论中的数学归纳法具有自己的特色.例 8 设有个罐子,在每一个罐子中各有个白球与个黑球,从第一个罐子中nmk任取一球放入第二个罐子中,并依此类推,求从最后一个罐子中取出一个白球的概率.解析 先探索规律,设2n令“从第一个罐子中取出一个球,是白球”1H“从第二个罐子中取出一个球,是白球”2H显然,所求概率kmmHP)(1|+|212()()(HPHPHP)1H21()(HPHP)1H kmmkmmkmkkmmkmm111这恰与时的结论是一样的,于是可以预见,不管是什么自然数,所求的概率都应1nn是,则当时,有kmm1 tn|+|11()()(tttHPHPHP)tH1()(ttHPHP)tH .kmmkmmkmkkmmkmm111于是,结论对所有自然数都成立.kmmHPn)(6 结束语 毕业设计,也许是我大学生涯交上的最后一个作业了.想籍次机会感谢四年以来给我帮助的所有老师、同学,你们的友谊是我人生的财富,是我生命中不可或缺的一部分.我的毕业论文指导老师孙彩云老师,虽然我们是在开始毕设时才认识,但她却能以一位长辈的风范来容谅我的无知和冲动,给我不厌其烦的指导.在此,特向她道声谢 晋中学院 XX 学院 20XX 届本科生毕业论文15谢.大学生活即将匆匆忙忙地过去,但我却能无悔地说:“我曾经来过.”大学四年,但它给我的影响却不能用时间来衡量,这四年以来,经历过的所有事,所有人,都将是我以后生活回味的一部分,是我为人处事的指南针.就要离开学校,走上工作的岗位了,这是我人生历程的又一个起点,在这里祝福大学里跟我风雨同舟的朋友们,一路走好,未来总会是绚烂缤纷.参考文献1 冯进.数学归纳法的发展历程N.常熟理工学院学报,2008,22(8):2122.2 刘艳.数学归纳法的原理及应用J.山西经济管理干部学院学报,2011,19(3):135136.3 程克玲.数学归纳法及其应用J.赤峰学院学报,2011,27(3):2223.4 王仁发,代数与解析几何M.长春:东北师范大学出版社,1999.5 陈丽,刘晓霞.离散数学M,北京:高等教育出版社,2002.5 王树禾.图论M.北京:科学出版社,2009.6 刘西垣,李永乐等.2012 年李永乐李正元考研数学复习全书M.北京:国家行政学院出版社,2009.