數學歸納法是壹種數學證明方法，典型地用於確定壹個表達式在所有自然數範圍內是成立的或者用於確定壹個其他的形式在壹個無窮序列是成立的。有壹種用於數理邏輯和計算機科學廣義的形式的觀點指出能被求出值的表達式是等價表達式；這就是著名的結構歸納法。 已知最早的使用數學歸納法的證明出現於 Francesco Maurolico 的 Arithmeticorum libri duo (1575年)。Maurolico 證明了前 n 個奇數的總和是 n^2。 最簡單和常見的數學歸納法證明方法是證明當n屬於所有自然數時壹個表達式成，這種方法是由下面兩步組成: 遞推的基礎: 證明當n = 1時表達式成立。 遞推的依據: 證明如果當n = m時成立，那麽當n = m + 1時同樣成立。(遞推的依據中的“如果”被定義為歸納假設。 不要把整個第二步稱為歸納假設。) 這個方法的原理在於第壹步證明起始值在表達式中是成立的，然後證明壹個值到下壹個值的證明過程是有效的。如果這兩步都被證明了，那麽任何壹個值的證明都可以被包含在重復不斷進行的過程中。或許想成多米諾效應更容易理解壹些；如果妳有壹排很長的直立著的多米諾骨牌那麽如果妳可以確定： 第壹張骨牌將要倒下。 只要某壹個骨牌倒了,與他相臨的下壹個骨牌也要倒。 那麽妳就可以推斷所有的的骨牌都將要倒。 數學歸納法的原理作為自然數公理，通常是被規定了的(參見皮亞諾公理第五條)。但是它可以用壹些邏輯方法證明；比如，如果下面的公理： 自然數集是有序的 被使用。 註意到有些其他的公理確實的是數學歸納法原理中的二者擇壹的公式化。更確切地說，兩個都是等價的。 用數學歸納法進行證明的步驟： （1）（歸納奠基）證明當 取第壹個值 時命題成立；證明了第壹步，就獲得了遞推的基礎，但僅靠這壹步還不能說明結論的普遍性.在第壹步中，考察結論成立的最小正整數就足夠了，沒有必要再考察幾個正整數，即使命題對這幾個正整數都成立，也不能保證命題對其他正整數也成立； （2）（歸納遞推）假設 時命題成立，證明當 時命題也成立；證明了第二步，就獲得了遞推的依據，但沒有第壹步就失去了遞推的基礎.只有把第壹步和第二步結合在壹起，才能獲得普遍性的結論； （3）下結論：命題對從 開始的所有正整數 都成立。 註： （1）用數學歸納法進行證明時，“歸納奠基”和“歸納遞推”兩個步驟缺壹不可； （2）在第二步中，在遞推之前， 時結論是否成立是不確定的，因此用假設二字，這壹步的實質是證明命題對 的正確性可以傳遞到 時的情況.有了這壹步，聯系第壹步的結論（命題對 成立），就可以知道命題對 也成立，進而再由第二步可知 即 也成立，…，這樣遞推下去就可以知道對於所有不小於 的正整數都成立.在這壹步中， 時命題成立，可以作為條件加以運用，而 時的情況則有待利用歸納假設、已知的定義、公式、定理加以證明，不能直接將 代入命題. 例子： 比如證明：1+2+3+4+……+n=n*(n+1)/2 先證明n=1時成立，n=1時，左式=1，右式=1*(1+1)/2=1,左右相等，證明，當n=1時，等式成立。 假設n=n時，等式成立，只要再證明n=n+1時，等式成立，則說明n=任何自然數時，等式都成立。（因為n=1成立，那麽如果n=1+1也成立，就說明n=2時也成立，如果n=2成立 ，那麽如果n=2+1也成立，就說明n=3時也成立，如果n=n時成立，那麽如果n=n+1時成立，那麽說明n+1時，等式也成立。） 當n=n時，1+2+3+…+n=n*(n+1)/2,(假設的) 當n=n+1時，左式=1+2+3+…+n+（n+1）=n*(n+1)/2+（n+1）， 經過分解因式、合並同類項，得到（n+1）* （n+1+1）/2，是不是等於（n+1）*[（n+1）+1]這個公式呢？ 於是推出，當n=n+1時，等式成立。 所以等式在任何自然數下都成立。 還不明白？因為n=1成立，n=2=1+1也能證明成立，……，n=n+1成立，所以麽……
參考資料：
/view/284458.htm