什么是數(shù)學(xué)歸納法?

數(shù)學(xué)歸納法是一種數(shù)學(xué)證明方法，典型地用于確定一個(gè)表達(dá)式在所有自然數(shù)范圍內(nèi)是成立的或者用于確定一個(gè)其他的形式在一個(gè)無(wú)窮序列是成立的。有一種用于數(shù)理邏輯和計(jì)算機(jī)科學(xué)廣義的形式的觀點(diǎn)指出能被求出值的表達(dá)式是等價(jià)表達(dá)式；這就是著名的結(jié)構(gòu)歸納法。

已知最早的使用數(shù)學(xué)歸納法的證明出現(xiàn)于 Francesco Maurolico 的 Arithmeticorum libri duo (1575年)。Maurolico 證明了前 n 個(gè)奇數(shù)的總和是 n^2。

最簡(jiǎn)單和常見(jiàn)的數(shù)學(xué)歸納法證明方法是證明當(dāng)n屬于所有自然數(shù)時(shí)一個(gè)表達(dá)式成，這種方法是由下面兩步組成:

遞推的基礎(chǔ): 證明當(dāng)n = 1時(shí)表達(dá)式成立。

遞推的依據(jù): 證明如果當(dāng)n = m時(shí)成立，那么當(dāng)n = m + 1時(shí)同樣成立。(遞推的依據(jù)中的“如果”被定義為歸納假設(shè)。 不要把整個(gè)第二步稱(chēng)為歸納假設(shè)。)

這個(gè)方法的原理在于第一步證明起始值在表達(dá)式中是成立的，然后證明一個(gè)值到下一個(gè)值的證明過(guò)程是有效的。如果這兩步都被證明了，那么任何一個(gè)值的證明都可以被包含在重復(fù)不斷進(jìn)行的過(guò)程中?；蛟S想成多米諾效應(yīng)更容易理解一些；如果你有一排很長(zhǎng)的直立著的多米諾骨牌那么如果你可以確定：

第一張骨牌將要倒下。

只要某一個(gè)骨牌倒了,與他相臨的下一個(gè)骨牌也要倒。

那么你就可以推斷所有的的骨牌都將要倒。

數(shù)學(xué)歸納法的原理作為自然數(shù)公理，通常是被規(guī)定了的(參見(jiàn)皮亞諾公理第五條)。但是它可以用一些邏輯方法證明；比如，如果下面的公理：

自然數(shù)集是有序的

被使用。

注意到有些其他的公理確實(shí)的是數(shù)學(xué)歸納法原理中的二者擇一的公式化。更確切地說(shuō)，兩個(gè)都是等價(jià)的。

用數(shù)學(xué)歸納法進(jìn)行證明的步驟：
（1）（歸納奠基）證明當(dāng) 取第一個(gè)值 時(shí)命題成立；證明了第一步，就獲得了遞推的基礎(chǔ)，但僅靠這一步還不能說(shuō)明結(jié)論的普遍性.在第一步中，考察結(jié)論成立的最小正整數(shù)就足夠了，沒(méi)有必要再考察幾個(gè)正整數(shù)，即使命題對(duì)這幾個(gè)正整數(shù)都成立，也不能保證命題對(duì)其他正整數(shù)也成立；

（2）（歸納遞推）假設(shè) 時(shí)命題成立，證明當(dāng) 時(shí)命題也成立；證明了第二步，就獲得了遞推的依據(jù)，但沒(méi)有第一步就失去了遞推的基礎(chǔ).只有把第一步和第二步結(jié)合在一起，才能獲得普遍性的結(jié)論；

（3）下結(jié)論：命題對(duì)從 開(kāi)始的所有正整數(shù) 都成立。

注：
（1）用數(shù)學(xué)歸納法進(jìn)行證明時(shí)，“歸納奠基”和“歸納遞推”兩個(gè)步驟缺一不可；

（2）在第二步中，在遞推之前， 時(shí)結(jié)論是否成立是不確定的，因此用假設(shè)二字，這一步的實(shí)質(zhì)是證明命題對(duì) 的正確性可以傳遞到 時(shí)的情況.有了這一步，聯(lián)系第一步的結(jié)論（命題對(duì) 成立），就可以知道命題對(duì) 也成立，進(jìn)而再由第二步可知 即 也成立，…，這樣遞推下去就可以知道對(duì)于所有不小于 的正整數(shù)都成立.在這一步中， 時(shí)命題成立，可以作為條件加以運(yùn)用，而 時(shí)的情況則有待利用歸納假設(shè)、已知的定義、公式、定理加以證明，不能直接將 代入命題.

例子：
比如證明：1+2+3+4+……+n=n*(n+1)/2
先證明n=1時(shí)成立，n=1時(shí)，左式=1，右式=1*(1+1)/2=1,左右相等，證明，當(dāng)n=1時(shí)，等式成立。
假設(shè)n=n時(shí)，等式成立，只要再證明n=n+1時(shí)，等式成立，則說(shuō)明n=任何自然數(shù)時(shí)，等式都成立。（因?yàn)閚=1成立，那么如果n=1+1也成立，就說(shuō)明n=2時(shí)也成立，如果n=2成立 ，那么如果n=2+1也成立，就說(shuō)明n=3時(shí)也成立，如果n=n時(shí)成立，那么如果n=n+1時(shí)成立，那么說(shuō)明n+1時(shí)，等式也成立。）
當(dāng)n=n時(shí)，1+2+3+…+n=n*(n+1)/2,(假設(shè)的)
當(dāng)n=n+1時(shí)，左式=1+2+3+…+n+（n+1）=n*(n+1)/2+（n+1），
經(jīng)過(guò)分解因式、合并同類(lèi)項(xiàng)，得到（n+1）* （n+1+1）/2，是不是等于（n+1）*[（n+1）+1]這個(gè)公式呢？
于是推出，當(dāng)n=n+1時(shí)，等式成立。
所以等式在任何自然數(shù)下都成立。
還不明白？因?yàn)閚=1成立，n=2=1+1也能證明成立，……，n=n+1成立，所以么……