自然数之数学归纳法课件.ppt

1、0.数学归纳法的背景 数学归纳法是数学中最基本也是最重要的方法之一.它在数学各个分支里都有广泛应用.该法的实质在于:将一个无法(或很难)穷尽验证的命题转化为证明两个普通命题:“p(1)真”和“若p(k)真,则p(k+1)真”,从而达到证明的目的. 数学归纳法早期叫逐次归纳法(始见于英国数学家摩根)或完全归纳法(始见于德国数学家戴德金).但后来人们更喜欢用数学归纳法的名称.因为它更能体现论证的严格性和科学性,又不与逻辑学中的“归纳法”混淆. 数学史上最早使用数学归纳法的人首推法国数学家帕斯卡,但他并未确立方法的理论依据.直到意大利数学家皮亚诺建立了自然数的理论,才标志着数学归纳法逻辑基础的奠定.

2、 摩根(Morgan,1806-1871)英国著名数学家,所著的代数学是我国第一本代数学译本. 负数的认识问题:摩根不承认负数.1831年,摩根在他的论数学的研究和困难中仍坚持认为负数是荒谬的. 四色猜想:四色猜想是世界近代三大数学难题之一.1852年,刚从伦敦大学毕业的弗南西斯葛斯里在对英国地图着色时发现,对无论多么复杂的地图,只需用四种颜色就足够将相邻的区域分开.这个千万人屡见不鲜的有趣事实引起了他的注意,他感到这种现象决非偶然,可能隐藏着深刻的科学道理.他把他的想法告诉了他的哥哥弗德雷克.弗德雷克是著名数学家摩根的学生,他对这个问题极感兴趣,于是便设法证明.可是,尽管他绞尽脑汁,仍百思不

3、得其解,于是他以“四色定理”为名,请他的老师摩根证明. 摩根也无法解决这个问题,于是德摩根写信请著名数学家哈密尔顿帮助解答,这位智慧超群的人也被这个简单的问题弄得一筹莫展,他冥思苦想了13年,直至逝世仍毫无结果. 在1876年,当时很有名望的数学家凯莱在数学年会上把这个问题归纳为“四色猜想”提出,并征求问题的解答.于是“四色猜想”开始引人注目. 1976年,美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上,用了1200个小时,作了100亿判断,终于完成了四色定理的证明.四色猜想的计算机证明,轰动了世界.它不仅解决了一个历时100多年的难题,而且有可能成为数学史上一系列新思维的起

4、点.不过也有不少数学家并不满足于计算机取得的成就,他们还在寻找一种简捷明快的书面证明方法. 戴德金(Dedekind,18311916),最伟大的德国数学家、理论家和教育家,近代抽象数学的先驱. 由无理数引发的数学危机一直延续到19世纪.直到1872年,德国数学家戴德金从连续性的要求出发,用有理数的“分割”来定义无理数,并把实数理论建立在严格的科学基础上,才结束了无理数被认为“无理”的时代,也结束了持续2000多年的数学史上的第一次大危机. 戴德金分割:假设给定某种方法,把所有的有理数分为两个集合，A和B，A中的每一个元素都小于B中的每一个元素,任何一种分类方法称为有理数的一个分割.对于任一分

5、割,必有3种可能,其中有且只有1种成立: 1.A有一个最大元素a,B没有最小元素(例如A是所有1的有理数.B是所有1的有理数). 2.B有一个最小元素b,A没有最大元素(例如A是所有1的有理数.B是所有1的有理数). 3.A没有最大元素,B也没有最小元素(例如A是所有负的有理数,零和平方小于2的正有理数,B是所有平方大于2的正有理数).显然A和B的并集是所有的有理数,因为平方等于2的数不是有理数. 注:A有最大元素a,且B有最小元素b是不可能的,因为这样就有一个有理数不存在于A和B两个集合中,与A和B的并集是所有的有理数矛盾.第3种情况,戴德金称这个分割为定义了一个无理数,或者简单的说这个分割

6、是一个无理数.前面2种情况中,分割是有理数.皮亚诺公理.,.,1.:,. 5).:(. 4).1:( 1. 3.,. 2.1 . 1包含一切自然数则集合数直接后继那么它的一个如果自然数自然数如果它具有下列性质是自然数的一个集合设数直接后继一自然数的每一自然数只能是另唯表示由数直接后继不是任何自然数的表示数直接后继有一个确定的每个自然数在自然数集合中是一个自然数MMaMaiiMiMbabaaaa其中的第5条公理又叫做归纳公理,它是数学归纳法的依据. 最小数定理 自然数的任何非空集合A必有一个最小数,即这个数小于集合A中所有其他的数. 证明:由于A不是空集,其中必含有一个自然数.我们在A中任取一个

7、数m,因为从1到m共有m个自然数,所以在A中不大于m的数最多只有m个.显然在这有限个数中存在着最小的数,我们用l来代表它.那么,l就是A中最小的数.事实上,l对于A中不大于m的数来说,它是最小的;而A中其余的数都比m大,因而更比l大,所以l就是A中最小的数.1.数学归纳法的基本形式.)(),() 1(,)(2);() 1 (1,)(:都成立对一切自然数则归纳成立可以推出成立假设奠基成立若的命题是关于自然数设第一数学归纳法nnPkPkPPnnPoo: .)() 1 (1,1, 1 , 0)(变着第一数学归纳法有如下取代成立应由成立中则上定义在集合如果rPPrNnPo.)(),()(,)(2);(

8、)(,),2(),1 (1,)(:都成立对一切自然数则归纳成立可以推出成立假设奠基成立若的命题是关于自然数设跳跃数学归纳法nnPlkPkPlPPPnnPoo.)(),()(,)1)(,)(2);() 1 (1,)(:都成立对一切自然数则归纳成立可以推出成立时为任意自然数假设奠基成立若的命题是关于自然数设第二数学归纳法nnPlkPknnPkknPnnPoo2.数学归纳法的证题技巧).) 1(,),2(),1 ()(),)(0(,) 1(,),2(),1 (,) 1 (),(: )1 (应另行证明这时或将起点后移至如果有意义起点前移至这时可考虑到将的过程中去归纳不能统一到或者困难比较验证的命题有些

9、关于自然数起点后移或起点前移rPPPrPPrPPPPnPn.)(,)(),(,),(),(,: )2(00000成立推出成立第二步假设即第一步验证的方法跨度考虑加大在采用数学归纳法时应命题上的对于定义在跨度加大rkPMkkPnPnPNmrnmrnrnnM.,.2 ,1:.,:)3(到适宜的解决方案才又可能找大胆猜测细心探索只有抓住命题的特点到何种程度为宜加强一个命题的结论加强结论将命题一般化法加强命题通常有两种方明比较方便而可能用数学归纳法证通过加强命题后反纳法证明的命题有些不易直接用数学归加强命题oo.), 7(53. 1邮资角的角的邮票可支付任何角和试证用面值为例Nnnn.7,.1.132

10、5,5;15233,3,3.), 7()2(.,8) 1 ( :立的任何自然数命题都成对综上时命题也成立故当角邮资角票就仍可支付张角票换成只要将一张角票邮资中至少有一张角若这角邮资角票就可支付张角票换成张将张则至少有付角票支角邮资全用若这时命题成立假设当结论显然成立时当证nknkkkkNkkknn.),1(:法来证明也可采用跳跃数学归纳了分类讨论的方法这里采用从归纳假设过度到上述证明的关键是如何说明kP.) 1 (,3.), 7()2(.5510, 3339 , 538,10, 9 , 8) 1 ( :归纳假设知显然成立及由时则当时命题成立假设当知命题成立由时当另证knNkkknn. 0,:,

11、35,3, 2, 1. 21221122121nnnnnnnnnnanaaaaaaaaanaa都有对一切正整数证明为奇数若为偶数若时当已知例)4(mod3),4(mod2),4(mod1,., 1 , 3 , 2 , 1 , 3 , 2 , 1 , 3 , 2 , 1, 4,4, 0.,163,17,26,49,23,22,29, 7 , 2 , 1:31323nnnaaan 有于是猜测对正整数考察所得的余数进而把这些数除以的倍数而且它们中没有不是它们都先观察一些初始值分析. 0,4.,.1.)4(mod3)4(mod31035)4(mod2)4(mod31)4(mod1)4(mod61535

12、).4(mod3),4(mod2),4(mod1,).4(mod3),4(mod2),4(mod1,1:132333)1(3313231)1(3133132)1(331323321nnkkkkkkkkkkkkkkkaanknaaaaaaaaaaaaaaaknaaan故的倍数都不是从而猜测正确从而对一切正整数正确即于是有时假设显然有时证明).121arctan()2121arctan(21arctan. 322nSn求例.1,1) 1(1arctan1) 1(1tan)4) 1(121arctan,1arctan0() 1(121arctan1arctan,1arctan.1:11221时成立即

13、则时有假设当时显然成立当证明knkkSkkSkkkkkkSkkSknnkkkk.,.,.:予严格的论证然后再用数学归纳法给得出来的不完全归纳等往往是经过一些推导、当然不是瞎猜猜出来的猜先都是许多结果、定理的发现要方法先猜后证是数学中的重注意.1arctan43arctan ,32arctan4)2121arctan(,21arctan0,32tan)2121arctan(21arctan: ,21arctan:3222221nnSSSSSSn由此猜测，同样过程又过程猜测结论1222)(,:. 111,. 4nnnnnbabanbaba都有对一切正整数求证且是正实数已知例.,.1,2222222

14、)22(4)()(, 42111.22)(,.,1:2)1(213221211112命题都成立对一切正整数综上时也成立即命题在从而所以，因为即时命题成立假设命题显然成立时证明nknabbaabbabababababaababbaababbabababaknnkkkkkkkkkkkkkkkkkkkkkk).1(,)() 1(,) 1(,) 1()(kpkpkpkpkpkp从而证得题的组合以及其他一些简单命转化为设法从中把着手我们可以从并不容易直接推导有时从归纳假设.:. 5倒数之和整数的都可以表示成不同的正任意正的真分数证明例nm.,.,1111.,111.1,0.,1,0.0 ,.)(.,1.

15、)(:121121命题成立综上所述此时命题也成立其中故是互不相等的正整数其中有归纳假设有时当命题成立此时时当是正整数其中令由于的正整数都成立假设命题对小于命题显然成立时当进行归纳对证明ttttqnqnqqnqnqnqnknnnnnnrnqrqnqrnnkrqqkknkqknrkrqrqknnknkmnm.:,)(0. 62113naaaaNnnnjjnjjn求证且有已知对任意例.,.1).(10) 1(, 0,2) 1(, 2 , 1,.22)()()()(,1, 2 , 1,., 10,1:111211121113121112121121111331213113113112131命题都成立对

16、一切正整数综上所述时也成立即命题在舍去或故又因为所以因为因为时当即时命题成立假设命题成立及由时证明nknkakakkaaakkakjjaaaaaaaaaaaaaaaaaaknkjjaknaaaankkkkkkjjjkkjjkkkkjjkkjjkkjjkjjkjjkkjjkkjjkjjj.) 1()(,),2(),1 (,) 1()(,.真都真而是由真真第二步并非由我们看到纳法本例用的是第二数学归kpkpppkpkp.,:,016,. 721221都是整数对任何正整数试证的两个根是方程设例nnxxnxxxx.,.)()(6)()()()(6,1, 1.34262)(,2,6,1:12112112

17、1112111211121121121121211211212121211211221221222121命题都成立对一切正整数综上所述也是整数所以时则当都是整数与即时命题成立假设也是整数时当为整数时当证明nxxxxxxxxxxxxxxxxxxxxxxxxxxxxknxxxxknknxxxxxxnxxnkkkkkkkkkkkkkkkkkkkkkkkkkk.)2(),1 (.) 1()(),1(真初始值故需检验两个真真本例用的归纳递推是由ppkpkpkp.,:. 822都有正整数解方程对任意正整数证明例nzyxn.,.2,)(,.,.2 , 1,. 5, 4, 3,2.,1:22111212020

18、2020212101001001220000002020000命题都成立对一切正整数综上所述时命题也成立即的一组正整数解为方程取的一组正整数解即为方程时命题成立假设时命题成立当由此可知例如取一组勾股数即可时当程的一组解即为方则并取任取正整数时当证明nknzyxzyxzzyxzyxzzzyyzxxzyxzyxknnzyxnzyxyxzyxnkkkk.,.)2)(,)(,.) 1()(1,) 1()(,前进然后按步长个起点我们需在奠基时验证此时成立只能推出成立的前提下在但对有些命题过度向由为步长即每次以成立成立去推我们是依据通常llllkpkpkpkpkpkp).32(2,2:.1211. 932

19、2naaaannannn时当证设例.,.) 1 ( ,2.11)132(2) 1(1)132(2) 1(11)132(2) 1(1)11(121)32(2) 1(112)11(.)2(.) 1 (, 22121121)2(2 ,49)211 (,2).1 (1)32(2:1322213221322132222212222322原命题也成立综上式也成立时即则时命题成立假设式成立故时当我们把命题加强为证明knkkaaakkkkkaaakkkaaakkakkkaaakkaakaaknaannnaaaakkkkkkkkknn.,:,法从而便于应用数学归纳结论加强二是把原命题的一是将原命题一般化通常有两

20、种情形更强的命题题我们可采取证明比原命大容易直接证明所给的命题不有时候.1:.,1993, 3 , 2 , 1.10调到列的第一位后把数可以通过上述若干操作试证个数反序重排则将此列的左端的前个数为若列中的第一依照某种顺序排成一列把正整数例kk.1993,1,)2(),1 (,.,)2(.,) 1 (.,1.,1., 2 , 1,:时记为本题结论当证明的目的数用归纳假设便可达到个这时只要对前面在未位的情况总可以得到通过因此不影响操作与未位数的位置对调而这时可将及未位数则这些操作都不涉都调不到首位无论如何若经过任何次操作便被调到未位则下次操作被调到首位设经过有限次的操作后个数的列结论也成立下证对结

21、论成立个数的列假设对显然成立时当个数用数学归纳法的对我们把命题一般化证明nnnnnnnnnnnn.,:,法从而便于应用数学归纳结论加强二是把原命题的一是将原命题一般化通常有两种情形更强的命题题我们可采取证明比原命大容易直接证明所给的命题不有时候三个著名的无理数0.无理数的产生第一次数学危机初等无理数复合无理数代数数和e的出现现在无理数定义 “有理数”中的“有理”一词,英文是Rational.这个词本来有两个含义,其一是“比”,其二是“合理”.照数学上的原义,分数可以表示成两个整数之比,整数也可以看作是这个整数与1的比,把“有理数”叫做“比数”应该是很贴切的.由于无理数不能表示为两个整数的比,因

22、此可以把“无理数”叫做“非比数”.可是,日本学者在十九世纪翻译西方的数学书时,把这个词译成了“有理数”.后来,在中日文化交流中,中国又从日本引进了“有理数”和“无理数”这两个词,长期应用到现在,没法改,也没必要改了. 1. 公元263年,我国三国时期的著名数学家刘徽首创利用圆内接正多边形的面积接近于圆的面积的方法来计算圆周率.当时刘徽算到内接正3072边形的面积,并求出3.1416.为纪念他,后人将之称为徽率. 公元460年,我国南朝数学家祖冲之,采用刘徽割圆术方法,一直算到圆内接正12288多边形的面积,并求出3.1415926. 1593年,荷兰数学家罗梅,也采用刘徽割圆术方法,计算到圆内

23、接正230多边形的面积,并求得的准确值到小数点后第15位. 1946年,曼切斯顿大学的费林生把计算到小数点后808位.后来,由于计算机的问世,才使得小数点后808位成了人工计算值的最高纪录. 目前最新结果是,日本东京的金田正康已将计算到小数点后133554000位. 1777年,法国数学家蒲丰宣布了一个惊人的发现:不需要用复杂的计算,只要你有足够的耐心,就能从一个投针的游戏中得出的近似值. ).(25. 2)211 (1 ,.25. 01,25. 1,).(75. 0%505 . 1,5 . 1,5 . 11,%50?,.%100,21,:2元元钱到一年时归还用算式表示即一年结算两次算一次半年

24、结元元利息多了比原来的元一年利息是这样元利益又收即到了年底再过半年元作为本金借给商人又把元元到半年时还即借因为半年的利率是利息岂不更多次帐财主想如果每半年结一即年利率为元元到一年时归还条件是每借商人向财主借钱事有一个关于高利贷的故 .,4 ,3,究竟能发多大的财账房先生算一算他便让不是发了大财甚至随时结算次次如果一年结算财主马上又想 ).(7181. 2)1000011 (1 ,100001,10000);(71692. 2)100011 (1 ,10001,1000);(59374. 2)1011 (1 ,101,10);(37037. 2)311 (1 ,31,3100001000103元

25、元钱到一年时归还利率为次结算元元钱到一年时归还利率为次结算元元钱到一年时归还利率为次结算元元钱到一年时归还利率为次结算2.e :,:一个名称数学家欧拉给这个上限一个上限需归还的钱总不能突破结算多少次不论这但增长得并不快也越多尽管结算次数越多利息结果使财主颇为失望 在今天的银行业里,e是对银行家最有帮助的一个数.人们可能会问,像e 这样的数是怎样又以何种方式与银行业发生关系呢?要知道后者是专门跟“元”和“分”打交道的! 假如没有e的发现,银行家要计算今天的利息就要花费大量的时间,无论是逐日逐日地算复利,还是持续地算复利都无法避免.所幸的是,e的出现助了一臂之力. .,.)1 (?.)11 (li

26、m.)11 (为存钱的年数次数为一年之内计算利息的为年利率本金为为本利和这里实际的计算公式是式呢算中怎样借助于这个公在利息计我们通常写为的极限的定义是作为数列tnrPAnrPAnenaentnnnn和e 这两个数的背景是很不一样的.与几何相联系;e与某种数量增减相联系,例如上述存款本息的增长以及生物繁殖等,亦可说,e是与分析相联系的. .! 41! 31! 21! 111),7151311 (4: )(,ee当然不可能是有限形式例如表示但它们都可以用有理数都是无理数与 e与的来源和背景不同,表现形式也不同,它们的小数表示也如此不同: =3.141 592 653 589 793 238 46

27、e=2.718 281 828 459 045 235 36 尽管如此,人们却在探寻人类最初碰到的这两个具有极其特殊地位的超越数之间有什么联系.首先人们看到一些现象:e与这两数的上述表示式中,第13位数同是9,第17 位数同是2,第18 位同是3,第21 位同是6,第34 位又同是2.人们甚至猜测每隔10 位数就会出现一个数相同.还有人猜测在的数字中必有e的前n位数字,在e的数字中必有的前n位数字.见张楚廷.数学文化.北京:高等教育出版社,2000.3. .61803. 02150111, 1.,:2xxxxxxxACABABC则如果令表示值用希腊字母这个比率的数划分了黄金分割被说成以则分点之

28、比于较长部分与较短部分之比等使整条线段与较长部分成两个部分如果我们把一条线段分的定义 古希腊人已知道黄金比率.黄金比率在希腊的建筑物中起着非常重要的作用.很多艺术家相信,在所有的矩形中,长宽之比为 的矩形的比例“最令人满意”,所以这个数在各种美学理论中起到了主要作用.令人惊奇的是,一些植物的叶片排列也显示出黄金比率.它有很多有趣的数学特性. .,),022,01(,2.,2,:22这种数属超然数方程的解不是任何整系数多项式与然而的解是的解是项式的解它们是具有整系数的多也就是说是代数数和同的两类数但它们却属于本质上不虽然都是无理数和注意exxxe超然数 证明e与是超然数并非易事,相对来说e容易一点,对于的超然性的证明则更难.1873 年法国数学家埃尔米特证明e是一个超然数,九年后德国的林德曼证明也是一个超然数.这种证明彻底地解决了“化圆为方”这一古老的问题.这可以说是人类最初具体认识到的两个超然数,虽然很久很久以前就知道有这样两个数(当初也并不是用符号e 和来表示的),但知道它们的超然性才不过一二百年的历史,这一认识是重要的历史跨越.