數(shù)學(xué)歸納法是一種數(shù)學(xué)證明方法,典型地用于確定一個(gè)表達(dá)式在所有自然數(shù)范圍內(nèi)是成立的或者用于確定一個(gè)其他的形式在一個(gè)無窮序列是成立的.有一種用于數(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)單和常見的數(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è)第二步稱為歸納假設(shè).)
這個(gè)方法的原理在于第一步證明起始值在表達(dá)式中是成立的,然后證明一個(gè)值到下一個(gè)值的證明過程是有效的.如果這兩步都被證明了,那么任何一個(gè)值的證明都可以被包含在重復(fù)不斷進(jìn)行的過程中.或許想成多米諾效應(yīng)更容易理解一些；如果你有一排很長(zhǎng)的直立著的多米諾骨牌那么如果你可以確定：
第一張骨牌將要倒下.
只要某一個(gè)骨牌倒了,與他相臨的下一個(gè)骨牌也要倒.
那么你就可以推斷所有的的骨牌都將要倒.
數(shù)學(xué)歸納法的原理作為自然數(shù)公理,通常是被規(guī)定了的(參見皮亞諾公理第五條).但是它可以用一些邏輯方法證明；比如,如果下面的公理：
自然數(shù)集是有序的被使用.