數(shù)學歸納法原理第二歸納法跳躍歸納法反向歸納法

1、數(shù)學歸納法原理(六種)：【第二歸納法】【跳躍歸納法】【反向歸納法】一行骨牌，如果都充分地靠近在一起（即留有適當間隔），那么只要推倒第一個，這一行骨牌都會倒塌；豎立的梯子，已知第一級屬于可到達的范圍，并且任何一級都能到達次一級，那么我們就可以確信能到達梯子的任何一級；一串鞭炮一經(jīng)點燃，就會炸個不停，直到炸完為止；，日常生活中這樣的事例還多著呢！數(shù)學歸納法原理 設P(n)是與自然數(shù)n有關的命題若 (I)命題P(1)成立；()對所有的自然數(shù)k，若P(k)成立，推得P(k+1)也成立. 由（I）、()可知命題P(n)對一切自然數(shù)n成立 我們將在“最小數(shù)原理”一章中介紹它的證明， 運用數(shù)學歸納法原理證題

2、的方法，是中學數(shù)學中的一個重要的方法，它是一種遞推的方法，它與歸納法有著本質的不同由一系列有限的特殊事例得出一般結論的推理方法，通常叫做歸納法，用歸納法可以幫助我們從具體事例中發(fā)現(xiàn)一般規(guī)律，但是，僅根據(jù)一系列有限的特殊事例得出的一般結論的真假性還不能肯定，這就需要采用數(shù)學歸納法證明它的正確性一個與自然數(shù)n有關的命題P(n)，常?？梢杂脭?shù)學歸納法予以證明，證明的步驟為：(I)驗證當n取第1個值no時，命題P(no)成立，這一步稱為初始驗證步()假設當n=k(kN，后no)時命題P(k)成立，由此推得命題P(k+1)成立這一步稱為歸納論證步()下結論，根據(jù)(I)、()或由數(shù)學歸納法原理斷定，對任何

3、自然數(shù)(nno)命題 P(n)成立這一步稱為歸納斷言步， 為了運用好數(shù)學歸納法原理，下面從有關注意事項與技巧及運用遞推思想解題等幾個方面作點介紹運用數(shù)學歸納法證題時應注意的事項與技巧三個步驟缺一不可第一步是遞推的基礎，第二步是遞推的依據(jù)，第三步是遞推的過程與結論三步缺一不可 數(shù)學歸納法的其他幾種形式還有：第二數(shù)學歸納法；跳躍數(shù)學歸納法；倒推數(shù)學歸納法（反向歸納法）；分段數(shù)學歸納法二元有限數(shù)學歸納法；雙向數(shù)學歸納法；蹺蹺板數(shù)學歸納法；同步數(shù)學歸納法等。1.5歸納法原理與反歸納法數(shù)學歸納法是中學教學中經(jīng)常使用的方法中學教材中的數(shù)學歸納法是這樣敘述的：如果一個命題與自然數(shù)有關，命題對n=1正確；若假

4、設此命題對n1正確，就能推出命題對n也正確，則命題對所有自然數(shù)都正確通俗的說法：命題對n=1正確，因而命題對n=2也正確，然后命題對n=3也正確，如此類推，命題對所有自然數(shù)都正確對于中學生來說，這樣形象地說明就足夠了；但是畢竟自然數(shù)是無限的，因而上述描述是不夠嚴格的，有了皮阿羅公理后，我們就能給出歸納法的嚴格證明1. 第一數(shù)學歸納定理1.19如果某個命題，它的敘述含有自然數(shù)，如果命題對n=1是正確的，而且假定如果命題對n的正確性就能推出命題對n+1也正確，則命題對一切自然數(shù)都成立（第一數(shù)學歸納 ）證明設是使所討論的例題正確的自然數(shù)集合，則(1) 設，則命題對n正確，這時命題對也正確，即(2)

5、所以由歸納公理，含有所有自然數(shù)，即命題對所有自然數(shù)都成立下面我們給出一個應用數(shù)學歸納法的命題例求證證明(1)當n=1時，有所以n=1，公式正確(2)假設當k=n時，公式正確，即那么當k=n時，有所以公式對n+1也正確在利用數(shù)學歸納法證明某些命題時，證明的過程往往歸納到n-1或n-2，而不僅僅是n-1，這時上述歸納法將失敗，因而就有了第二數(shù)學歸納法在敘述第二歸納法以前，我們先證明幾個與自然數(shù)有關的命題2. 第二數(shù)學歸納法命題若，則證明因為所以 所以 命題是自然數(shù)中最小的一個證明若，則有前元b，所以命題3 若，則（即數(shù)與是鄰接的兩個數(shù)，中間沒有其他自然數(shù)，不存在b，使得）證明若,則因為，所以，即由

6、上述有關自然數(shù)大小的命題，我們得出下面定理，有時也稱為最小數(shù)原理定理1.20自然數(shù)的任何非空集合含有一個最小數(shù)，即存在一個數(shù)，使得對集合中任意數(shù)b，均有證明 設M是這樣的集合：對于M中任意元素，對A中任意元素，均有則M是非空集合因為，由歸納公理(4)知，一定存在一個元素但，即，否則由得，這顯然不可能現(xiàn)在我們證明因為若，則中任意元素所以，與矛盾，所以m即為中最小元素上述定理也稱為最小數(shù)原則，有的作者把它當成公理，用它也可以證明數(shù)學歸納法，下面我們給出所謂第二數(shù)學歸納法（第二數(shù)學歸納法）定理1.21對于一個與自然數(shù)有關的命題，若(1)當n=時命題正確；(2)假設命題T對正確，就能推出命題T對正確則

7、命題T對一切自然數(shù)正確證明如果命題不是對所有自然數(shù)都成立，那么使命題不成立的自然數(shù)集合就是非空集合，由定理1.20，中含有一個最小數(shù)k，且（k=1命題正確），所以對一切,命題T成立，又由(2)推出命題T對k正確結論矛盾下面我們給出兩個只能應用第二數(shù)學歸納法而不能應用第一歸納法解題的例子例已知數(shù)列，有 且求證證明對n=1，有; 所以命題對n=1正確假設命題對正確，則所以命題對n=k正確由第二數(shù)學歸納法本題得證例已知任意自然數(shù)均有（這里）求證證明(1)當n=1時，由，得所以命題對n=1正確(2)假設對命題正確，這時，當n=k+1時， (1)但是 (2)又因為歸納假設對命題正確，所以所以 由(1)和

8、(2)式得消去，得 解得 舍去）所以命題對n=k+1也正確上邊的兩個例子，實際上例命題歸結到n-1和n-2，而例則需要歸結到1,2,k，由此可見，第二數(shù)學歸納法的作用是不能由第一歸納法所替代的現(xiàn)在我們繼續(xù)講數(shù)學歸納法當然，歸納并一定從n=1開始，例如例數(shù)列的例子，也可以從某數(shù)k開始數(shù)學歸納法還有許多變形，其中著名的有跳躍歸納法、雙歸納法、反歸納法以及蹺蹺板歸納法等，下面我們就逐個介紹這些歸納法3.跳躍歸納法若一個命題對自然數(shù),都是正確的；如果由假定命題對自然數(shù)k正確，就能推出命題對自然數(shù)正確則命題對一切自然數(shù)都正確證明因為任意自然數(shù)由于命題對一切中的r都正確，所以命題對都正確，因而對一切n命題

9、都正確下面我們給出一個應用跳躍歸納法的一個例子例4求證用面值3分和5分的郵票可支付任何n(n)分郵資證明顯然當n=8,n=9,n=10時，可用3分和5分郵票構成上面郵資（n=8時，用一個3分郵票和一個5分郵票，n=9時，用3個3分郵票，n=10時，用2個5分郵票）下面假定k=n時命題正確，這時對于k=n+3，命題也正確，因為n分可用3分與5分郵票構成，再加上一個3分郵票，就使分郵資可用3分與5分郵票構成由跳躍歸納法知命題對一切n都成立下面我們介紹雙歸納法，所謂雙歸納法是所設命題涉及兩個獨立的自然數(shù)對(m,n),而不是一個單獨的自然數(shù)n4. 雙歸納法若命題與兩個獨立的自然數(shù)對m與n有關，(1)若

10、命題對m=1與n=1是正確的；(2)若從命題對自然數(shù)對（m,n）正確就能推出該命題對自然數(shù)對（m+1,n）正確，和對自然數(shù)對（m,n+1）也正確則命題對一切自然數(shù)對（m,n）都正確關于雙歸納法的合理性證明我們不予說明，只給出一個例子例求證對任意自然數(shù)m與n均有證明(1)當時，命題顯然正確，即(2)設命題對自然數(shù)對m與n正確，即這時 即命題對數(shù)對（m+1,n）正確；另一方面即命題對數(shù)對(m,n+1)也正確，由雙歸納法知，命題對一切自然數(shù)對(m,n)都成立5. 反歸納法若一個與自然數(shù)有關的命題，如果(1)命題對無窮多個自然數(shù)成立；(2)假設命題對n=k正確，就能推出命題對n=k-1正確則命題對一切

11、自然數(shù)都成立；上述歸納法稱為反歸納法，它的合理性我們做如下簡短說明：設是使命題不正確的自然數(shù)，如果是非空集合，則中存在最小數(shù)m，使得命題對k=m不正確；由于命題對無窮多個自然數(shù)正確，所以存在一個，且命題T對正確；由于命題T對m不正確，所以命題對也不正確，否則由命題T對正確就推出命題T對m正確矛盾！這樣，命題對m+2也不正確，經(jīng)過次遞推后，可得命題對也不正確這與已知矛盾，所以是空集合反歸納法又稱倒推歸納法，法國數(shù)學家柯西（1789-1857）首次用它證明了n個數(shù)的算術平均值大于等于這n個數(shù)的幾何平均值 例6 求證n個正實數(shù)的算術平均值大于或等于這n個數(shù)的幾何平均值，即證明 當n=2時，因此命題對

12、n=2正確當n=4時，因此命題對n=4正確同理可推出命題對n=23=8，n=24,，n=2s都正確（s為任意自然數(shù)），所以命題對無窮多個自然數(shù)成立設命題對nk正確，令則（容易證明上述是一個恒等式）由歸納假設命題對nk正確，所以所以 即 命題對n =k-1也正確，由反歸納法原理知，命題對一切自然數(shù)成立 由于上述不等式是著名不等式，我們再給出幾種證明：前已證明，命題對n=2m時正確，設nm，令這時我們有即命題對n2m正確利用數(shù)學歸納法證明不妨設n個數(shù)為，顯然當n=1時命題正確設命題對正確，令則 因為，所以所以命題對n=k+1正確，由第一歸納法知，命題對一切自然數(shù)成立另一個有趣的證明是由馬克羅林給出

13、的，我們知道，若保持和不變，以分別代替和，這時兩個數(shù)的和仍然是s，但兩個數(shù)的積卻增加了，即實際上兩個數(shù)的算術平均值大于幾何平均值，只有當兩個數(shù)相等時才有等號成立現(xiàn)在我們變動諸數(shù)，但保持它們的和不變，這時乘積必然在時取極大值因為若不等于，我們用分別代替與,則仍然不變，但它們的乘積卻增加了而當時，所以n個數(shù)的算術平均值大于等于幾何平均值下面我們給出應用上述不等式的例子例 在體積一定的圓柱形中，求其中表面積最小的一個（即在容積一定罐頭中，求表面積最小的一個）解 設圓柱的高為x，底圓半徑為y，體積為常數(shù)，表面積為，則其中為常數(shù)，欲求的極小值已知，所以即 顯然只有當時，取最小值即當x=2y時，值最小例

14、求證在所有具有相同面積的凸四邊形中，正方形的周長最短證明 用abcd表示四邊形的四條邊，為a與b的夾角，為c與d的夾角，用表示四邊形的面積，則由（2）式得 由（1）式得其中 再利用半角公式，得所以=如令四邊形周長，得因為，所以要使p最小（A為常數(shù)），只有當上式取等號時即當，且度，這樣的四邊形只能是正方形6. 最后，我們給出蹺蹺板歸納法有兩個與自然數(shù)有關的命題An與Bn，若(1)A1成立；(2)假設Ak成立，就推出Bk成立，假設Bk成立就推出Ak+1成立則對一切自然數(shù)n, An與Bn都成立這里我們只給出一個例子說明上述歸納法例已知求證證明令 ，(1)當n=1時，所以A1成立(2) 所以A2成立設

15、Ak成立，則即k成立若k成立，則即Ak+1成立由蹺蹺板歸納法知，一切An和Bn都成立.練習1.5(1)用數(shù)學歸納法證明(2)求證(3)已知，且，求證程序原理：【中途點法】【消數(shù)法】【消點法】現(xiàn)在，計算機已極大地普及，相當多的工作都由計算機來處理要計算機處理某個問題，首先就得將這個問題編成計算機語言編程因此，學習計算機常識少不了談論編程問題這個常識性問題中也蘊含了我們解數(shù)學問題的一個基本原理程序原理 這條原理要求做事情應按照一定的程序步驟，這個原理和切分原理一樣，是不需要證明而為人們承認，并得到廣泛運用的 在運用這個原理時，要注意如下幾點： (1)分步的有效性完成這件事的任何一種方法，都要分成幾

16、個步驟執(zhí)行，因此，首先要根據(jù)問題的特點確定一個分步標準，標準不同，分成的步驟也可能不同各個步驟是相互依存的，必須而且只能連續(xù)完成各步驟，這件事才告完成 (2)過程的確定性，把這幾個步驟看做一個過程，任何一種解決方法都可歸結為這幾個步驟形成的過程，而無其他過程 (3)選擇的均等性對于每一個i（i=1，2，n-1），第i步中的每一種方法在其后續(xù)步驟（第i+1步）中，均可選用mi+1種方法中的一種 (4)解答的準確性每一步的解答應盡可能準確，以避免“一著不慎，滿盤皆輸” 程序原理及其應用 程序原理I 解決一個問題（或做一件事），先將待解決的問題適當分解成程序步驟問題，最后按此程序步驟把問題解決，或把

17、一個處理問題的“全過程”恰當?shù)胤殖蓭讉€連接進行的較為簡單的“分過程”，最終獲得問題的解決，我們在數(shù)學解題中，運用的中途點法、消點法、消數(shù)法等都是程序原理I的體現(xiàn)中途點法 運用程序原理I解題，可以對某個數(shù)學問題在已知與結論之間建立若干小目標或中途點，亦即把原問題分解成一些有層次順序的小問題，逐個解決這些小問題，逐步達到一個后繼一個的小目標或中途點，最后使問題解決， 建立中途小目標，可采用倒推（如例1、例2）、順推（如例3、例4等）、兩頭推(如例5、例6)、猜測或嘗試（如例7）等手段 采用中途點法解題是我們解題的最基本方法之一它和分解迭加一樣，我們早就實踐了，在學習中有相當多的數(shù)學問題都可采用中途

18、點法解答，下面我們看幾個稍難一點兒的例子. 消數(shù)法 求解有關代數(shù)問題時，先將題設條件中的有關常數(shù)巧妙地消去，然后根據(jù)消去常數(shù)后的式子的特點，分解變形，推演等方式獲得所求的結果的方法，我們稱為消數(shù)法. 消點法 在研究幾何定理的機器證明中，張景中院士以他多年來發(fā)展的幾何新方法（面積法）為基本工具，提出了消點思想，和周咸青、高小山合作，于1992年突破了這項難題，實現(xiàn)了幾何定理可讀性證明的自動生成這一新方法既不以坐標為基礎，也不同于傳統(tǒng)的綜合方法，而是一個以幾何不變量為工具，把幾何、代數(shù)邏輯和人工智能方法結合起來所形成的開發(fā)系統(tǒng)它選擇幾個基本的幾何不變量和一套作圖規(guī)則并且建立一系列與這些不變量和作圖規(guī)則有關的消點公式，當命題的前提以作圖語句的形式輸入時，程序可調用適當?shù)南c公式把結論中的約束關系逐個消去，最后水落石出，消點的過程記錄與消點公式相結