各種數(shù)學(xué)歸納法.doc

1.5歸納法原理與反歸納法數(shù)學(xué)歸納法是中學(xué)教學(xué)中經(jīng)常使用的方法中學(xué)教材中的數(shù)學(xué)歸納法是這樣敘述的：如果一個(gè)命題與自然數(shù)有關(guān)，命題對(duì)n=1正確；若假設(shè)此命題對(duì)n1正確，就能推出命題對(duì)n也正確，則命題對(duì)所有自然數(shù)都正確通俗的說法：命題對(duì)n=1正確，因而命題對(duì)n=2也正確，然后命題對(duì)n=3也正確，如此類推，命題對(duì)所有自然數(shù)都正確對(duì)于中學(xué)生來說，這樣形象地說明就足夠了；但是畢竟自然數(shù)是無限的，因而上述描述是不夠嚴(yán)格的，有了皮阿羅公理后，我們就能給出歸納法的嚴(yán)格證明定理1.19如果某個(gè)命題，它的敘述含有自然數(shù)，如果命題對(duì)n=1是正確的，而且假定如果命題對(duì)n的正確性就能推出命題對(duì)n+1也正確，則命題對(duì)一切自然數(shù)都成立（第一數(shù)學(xué)歸納法）證明設(shè)是使所討論的例題正確的自然數(shù)集合，則(1) 設(shè)，則命題對(duì)n正確，這時(shí)命題對(duì)也正確，即(2) 所以由歸納公理，含有所有自然數(shù)，即命題對(duì)所有自然數(shù)都成立下面我們給出一個(gè)應(yīng)用數(shù)學(xué)歸納法的命題例求證證明(1)當(dāng)n=1時(shí)，有所以n=1，公式正確(2)假設(shè)當(dāng)k=n時(shí)，公式正確，即那么當(dāng)k=n時(shí)，有所以公式對(duì)n+1也正確在利用數(shù)學(xué)歸納法證明某些命題時(shí)，證明的過程往往歸納到n-1或n-2，而不僅僅是n-1，這時(shí)上述歸納法將失敗，因而就有了第二數(shù)學(xué)歸納法在敘述第二歸納法以前，我們先證明幾個(gè)與自然數(shù)有關(guān)的命題命題若，則證明因?yàn)樗运悦}是自然數(shù)中最小的一個(gè)證明若，則有前元b，所以命題3 若，則（即數(shù)與是鄰接的兩個(gè)數(shù)，中間沒有其他自然數(shù)，不存在b，使得）證明若,則因?yàn)?，所以，即由上述有關(guān)自然數(shù)大小的命題，我們得出下面定理，有時(shí)也稱為最小數(shù)原理定理1.20自然數(shù)的任何非空集合含有一個(gè)最小數(shù)，即存在一個(gè)數(shù)，使得對(duì)集合中任意數(shù)b，均有證明 設(shè)M是這樣的集合：對(duì)于M中任意元素，對(duì)A中任意元素，均有則M是非空集合因?yàn)椋蓺w納公理(4)知，一定存在一個(gè)元素但，即，否則由得，這顯然不可能現(xiàn)在我們證明因?yàn)槿?，則中任意元素所以，與矛盾，所以m即為中最小元素上述定理也稱為最小數(shù)原則，有的作者把它當(dāng)成公理，用它也可以證明數(shù)學(xué)歸納法，下面我們給出所謂第二數(shù)學(xué)歸納法（第二數(shù)學(xué)歸納法）定理1.21對(duì)于一個(gè)與自然數(shù)有關(guān)的命題，若(1)當(dāng)n=時(shí)命題正確；(2)假設(shè)命題T對(duì)正確，就能推出命題T對(duì)正確則命題T對(duì)一切自然數(shù)正確證明如果命題不是對(duì)所有自然數(shù)都成立，那么使命題不成立的自然數(shù)集合就是非空集合，由定理1.20，中含有一個(gè)最小數(shù)k，且（k=1命題正確），所以對(duì)一切,命題T成立，又由(2)推出命題T對(duì)k正確結(jié)論矛盾下面我們給出兩個(gè)只能應(yīng)用第二數(shù)學(xué)歸納法而不能應(yīng)用第一歸納法解題的例子例已知數(shù)列，有且求證證明對(duì)n=1，有所以命題對(duì)n=1正確假設(shè)命題對(duì)正確，則所以命題對(duì)n=k正確由第二數(shù)學(xué)歸納法本題得證例已知任意自然數(shù)均有（這里）求證證明(1)當(dāng)n=1時(shí)，由，得所以命題對(duì)n=1正確(2)假設(shè)對(duì)命題正確，這時(shí)，當(dāng)n=k+1時(shí)，(1)但是(2)又因?yàn)闅w納假設(shè)對(duì)命題正確，所以所以由(1)和(2)式得消去，得解得舍去）所以命題對(duì)n=k+1也正確上邊的兩個(gè)例子，實(shí)際上例命題歸結(jié)到n-1和n-2，而例則需要?dú)w結(jié)到1,2,k，由此可見，第二數(shù)學(xué)歸納法的作用是不能由第一歸納法所替代的現(xiàn)在我們繼續(xù)講數(shù)學(xué)歸納法當(dāng)然，歸納并一定從n=1開始，例如例數(shù)列的例子，也可以從某數(shù)k開始數(shù)學(xué)歸納法還有許多變形，其中著名的有跳躍歸納法、雙歸納法、反歸納法以及蹺蹺板歸納法等，下面我們就逐個(gè)介紹這些歸納法跳躍歸納法若一個(gè)命題對(duì)自然數(shù),都是正確的；如果由假定命題對(duì)自然數(shù)k正確，就能推出命題對(duì)自然數(shù)正確則命題對(duì)一切自然數(shù)都正確證明因?yàn)槿我庾匀粩?shù)由于命題對(duì)一切中的r都正確，所以命題對(duì)都正確，因而對(duì)一切n命題都正確下面我們給出一個(gè)應(yīng)用跳躍歸納法的一個(gè)例子例4求證用面值3分和5分的郵票可支付任何n(n)分郵資證明顯然當(dāng)n=8,n=9,n=10時(shí)，可用3分和5分郵票構(gòu)成上面郵資（n=8時(shí)，用一個(gè)3分郵票和一個(gè)5分郵票，n=9時(shí)，用3個(gè)3分郵票，n=10時(shí)，用2個(gè)5分郵票）下面假定k=n時(shí)命題正確，這時(shí)對(duì)于k=n+3，命題也正確，因?yàn)閚分可用3分與5分郵票構(gòu)成，再加上一個(gè)3分郵票，就使分郵資可用3分與5分郵票構(gòu)成由跳躍歸納法知命題對(duì)一切n都成立下面我們介紹雙歸納法，所謂雙歸納法是所設(shè)命題涉及兩個(gè)獨(dú)立的自然數(shù)對(duì)(m,n),而不是一個(gè)單獨(dú)的自然數(shù)n雙歸納法若命題與兩個(gè)獨(dú)立的自然數(shù)對(duì)m與n有關(guān)，(1)若命題對(duì)m=1與n=1是正確的；(2)若從命題對(duì)自然數(shù)對(duì)（m,n）正確就能推出該命題對(duì)自然數(shù)對(duì)（m+1,n）正確，和對(duì)自然數(shù)對(duì)（m,n+1）也正確則命題對(duì)一切自然數(shù)對(duì)（m,n）都正確關(guān)于雙歸納法的合理性證明我們不予說明，只給出一個(gè)例子例求證對(duì)任意自然數(shù)m與n均有證明(1)當(dāng)時(shí)，命題顯然正確，即(2)設(shè)命題對(duì)自然數(shù)對(duì)m與n正確，即這時(shí)即命題對(duì)數(shù)對(duì)（m+1,n）正確；另一方面即命題對(duì)數(shù)對(duì)(m,n+1)也正確，由雙歸納法知，命題對(duì)一切自然數(shù)對(duì)(m,n)都成立反歸納法若一個(gè)與自然數(shù)有關(guān)的命題，如果(1)命題對(duì)無窮多個(gè)自然數(shù)成立；(2)假設(shè)命題對(duì)n=k正確，就能推出命題對(duì)n=k-1正確則命題對(duì)一切自然數(shù)都成立；上述歸納法稱為反歸納法，它的合理性我們做如下簡(jiǎn)短說明：設(shè)是使命題不正確的自然數(shù)，如果是非空集合，則中存在最小數(shù)m，使得命題對(duì)k=m不正確；由于命題對(duì)無窮多個(gè)自然數(shù)正確，所以存在一個(gè)，且命題T對(duì)正確；由于命題T對(duì)m不正確，所以命題對(duì)也不正確，否則由命題T對(duì)正確就推出命題T對(duì)m正確矛盾！這樣，命題對(duì)m+2也不正確，經(jīng)過次遞推后，可得命題對(duì)也不正確這與已知矛盾，所以是空集合反歸納法又稱倒推歸納法，法國(guó)數(shù)學(xué)家柯西（1789-1857）首次用它證明了n個(gè)數(shù)的算術(shù)平均值大于等于這n個(gè)數(shù)的幾何平均值 例6 求證n個(gè)正實(shí)數(shù)的算術(shù)平均值大于或等于這n個(gè)數(shù)的幾何平均值，即證明 當(dāng)n=2時(shí)，因此命題對(duì)n=2正確當(dāng)n=4時(shí)，因此命題對(duì)n=4正確同理可推出命題對(duì)n=23=8，n=24,，n=2s都正確（s為任意自然數(shù)），所以命題對(duì)無窮多個(gè)自然數(shù)成立設(shè)命題對(duì)nk正確，令則（容易證明上述是一個(gè)恒等式）由歸納假設(shè)命題對(duì)nk正確，所以所以即命題對(duì)n =k-1也正確，由反歸納法原理知，命題對(duì)一切自然數(shù)成立 由于上述不等式是著名不等式，我們?cè)俳o出幾種證明：前已證明，命題對(duì)n=2m時(shí)正確，設(shè)nm，令這時(shí)我們有即命題對(duì)n2m正確利用數(shù)學(xué)歸納法證明不妨設(shè)n個(gè)數(shù)為，顯然當(dāng)n=1時(shí)命題正確設(shè)命題對(duì)正確，令則 因?yàn)椋运悦}對(duì)n=k+1正確，由第一歸納法知，命題對(duì)一切自然數(shù)成立另一個(gè)有趣的證明是由馬克羅林給出的，我們知道，若保持和不變，以分別代替和，這時(shí)兩個(gè)數(shù)的和仍然是s，但兩個(gè)數(shù)的積卻增加了，即實(shí)際上兩個(gè)數(shù)的算術(shù)平均值大于幾何平均值，只有當(dāng)兩個(gè)數(shù)相等時(shí)才有等號(hào)成立現(xiàn)在我們變動(dòng)諸數(shù)，但保持它們的和不變，這時(shí)乘積必然在時(shí)取極大值因?yàn)槿?，用分別代替與則仍然不變，但它們的乘積卻增加了而當(dāng)時(shí)，所以n個(gè)數(shù)的算術(shù)平均值大于等于幾何平均值下面我們給出應(yīng)用上述不等式的例子例 在體積一定的圓柱形中，求其中表面積最小的一個(gè)（即在容積一定罐頭中，求表面積最小的一個(gè)）解 設(shè)圓柱的高為x，底圓半徑為y，體積為常數(shù)，表面積為，則其中為常數(shù)，欲求的極小值已知，所以即顯然只有當(dāng)時(shí)，取最小值即當(dāng)x=2y時(shí)，值最小例 求證在所有具有相同面積的凸四邊形中，正方形的周長(zhǎng)最短證明 用abcd表示四邊形的四條邊，為a與b的夾角，為c與d的夾角，如圖用表示四邊形的面積，則由（2）式得 由（1）式得其中 再利用半角公式，得所以=如令四邊形周長(zhǎng)，得因?yàn)?，所以要使p最小（A為常數(shù)），只有當(dāng)上式取等號(hào)時(shí)即當(dāng)，且，這樣的四邊形只能是正方形最后，我們給出蹺蹺板歸納法有兩個(gè)與自然數(shù)有關(guān)的命題An與Bn，若(1)A1成立；(2)假設(shè)Ak成立，就推出Bk成立，假設(shè)Bk成立就