數(shù)學(xué)歸納法（Mathematical Induction, MI）是一種數(shù)學(xué)演繹推理方法。它主要用于證明某個(gè)命題在全部或部分自然數(shù)范圍內(nèi)的成立性，以探究特定規(guī)律或界定命題的適用范圍。數(shù)學(xué)歸納法不僅適用于自然數(shù)，也廣泛應(yīng)用于更一般的良基結(jié)構(gòu)的證明，如在四色猜想的證明中所展現(xiàn)的。即便在表面上沒(méi)有顯而易見(jiàn)的自然數(shù)遞推關(guān)系，數(shù)學(xué)歸納法仍然適用，特別是當(dāng)其深層結(jié)構(gòu)與自然數(shù)存在某種對(duì)應(yīng)關(guān)系時(shí)。比如，在集合論中用于樹(shù)的分析。這種廣義的數(shù)學(xué)歸納法稱(chēng)作結(jié)構(gòu)歸納法，可應(yīng)用于數(shù)學(xué)邏輯和計(jì)算機(jī)科學(xué)領(lǐng)域。此外，數(shù)學(xué)歸納法還有各種變形，例如皮耶·德·費(fèi)瑪的無(wú)窮遞降法，這是一種用于反證的數(shù)學(xué)歸納法。
簡(jiǎn)介
在數(shù)論中，數(shù)學(xué)歸納法是以一種不同的方式來(lái)證明任意一個(gè)給定的情形都是正確的（第一個(gè)，第二個(gè)，第三個(gè)，一直下去概不例外）的數(shù)學(xué)定理。
雖然數(shù)學(xué)歸納法名字中有“歸納”，但是數(shù)學(xué)歸納法并非不嚴(yán)謹(jǐn)?shù)?a href="/hebeideji/1887272743337596660.html">歸納推理法，它屬于完全嚴(yán)謹(jǐn)?shù)?a href="/hebeideji/8800196298879147366.html">演繹推理法。事實(shí)上，所有數(shù)學(xué)證明都是演繹法。
解題
原理
最簡(jiǎn)單和常見(jiàn)的數(shù)學(xué)歸納法是證明當(dāng)n等于任意一個(gè)自然數(shù)時(shí)某命題成立。證明分下面兩步：
這種方法的原理在于：首先證明在某個(gè)起點(diǎn)值時(shí)命題成立，然后證明從一個(gè)值到下一個(gè)值的過(guò)程有效。當(dāng)這兩點(diǎn)都已經(jīng)證明，那么任意值都可以通過(guò)反復(fù)使用這個(gè)方法推導(dǎo)出來(lái)。把這個(gè)方法想成多米諾骨牌效應(yīng)也許更容易理解一些。例如：你有一列很長(zhǎng)的直立著的多米諾骨牌，如果你可以：
那么便可以下結(jié)論：所有的骨牌都會(huì)倒下。
解題要點(diǎn)
數(shù)學(xué)歸納法對(duì)解題的形式要求嚴(yán)格，數(shù)學(xué)歸納法解題過(guò)程中，
第一步：驗(yàn)證n取第一個(gè)自然數(shù)時(shí)成立
第二步：假設(shè)時(shí)成立，然后以驗(yàn)證的條件和假設(shè)的條件作為論證的依據(jù)進(jìn)行推導(dǎo)，在接下來(lái)的推導(dǎo)過(guò)程中不能直接將代入假設(shè)的原式中去。
最后一步總結(jié)表述。
需要強(qiáng)調(diào)是數(shù)學(xué)歸納法的兩步都很重要，缺一不可，否則可能得到下面的荒謬證明：
證明1：所有的馬都是一種顏色
首先，第一步，這個(gè)命題對(duì)時(shí)成立，即，只有1匹馬時(shí)，馬的顏色只有一種。
第二步，假設(shè)這個(gè)命題對(duì)n成立，即假設(shè)任何n匹馬都是一種顏色。那么當(dāng)我們有匹馬時(shí)，不妨把它們編好號(hào)：
對(duì)其中（1、2……n）這些馬，由我們的假設(shè)可以得到，它們都是同一種顏色；
對(duì)這些馬，我們也可以得到它們是一種顏色；
由于這兩組中都有（2、3、……n）這些馬，所以可以得到，這種馬都是同一種顏色。
這個(gè)證明的錯(cuò)誤來(lái)于推理的第二步：當(dāng)時(shí)，，此時(shí)馬的編號(hào)只有1、2，那么分的兩組是（1）和（2）——它們沒(méi)有交集，所以第二步的推論是錯(cuò)誤的。數(shù)學(xué)歸納法第二步要求過(guò)程對(duì)的數(shù)都成立，而上面的證明就好比多米諾骨牌的第一塊和第二塊之間間隔太大，推倒了第一塊，但它不會(huì)推倒第二塊。即使我們知道第二塊倒下會(huì)推倒第三塊等等，但這個(gè)過(guò)程早已在第一和第二塊之間就中斷了。
證明2：舉例證明下面的定理
——等差數(shù)列求和公式
第一步，驗(yàn)證該公式在時(shí)成立。即有,，所以這個(gè)公式在時(shí)成立。
第二步，需要證明假設(shè)時(shí)公式成立，那么可以推導(dǎo)出時(shí)公式也成立。步驟如下：
假設(shè)時(shí)公式成立，即（等式1）
然后在等式兩邊同時(shí)分別加上得到（等式2）
這就是時(shí)的等式。我們下一步需要根據(jù) 等式1證明 等式2 成立。通過(guò)因式分解合并，等式2的右邊也就是這樣我們就完成了由成立推導(dǎo)出成立的過(guò)程，證畢。
結(jié)論：對(duì)于任意自然數(shù)n，公式均成立。
對(duì)于以上例2的分析
在這個(gè)證明中，歸納的過(guò)程如下：
合理性
數(shù)學(xué)歸納法的原理，通常被規(guī)定作為自然數(shù)公理（參見(jiàn)皮亞諾公理）。但是在另一些公理的基礎(chǔ)上，它可以用一些邏輯方法證明。數(shù)學(xué)歸納法原理可以由下面的良序性質(zhì)（最小自然數(shù)原理）公理可以推出：
自然數(shù)集是良序的。（每個(gè)非空的正整數(shù)集合都有一個(gè)最小的元素）
比如這個(gè)正整數(shù)集合中有最小的數(shù)——1.
下面我們將通過(guò)這個(gè)性質(zhì)來(lái)證明數(shù)學(xué)歸納法：
對(duì)于一個(gè)已經(jīng)完成上述兩步證明的數(shù)學(xué)命題，我們假設(shè)它并不是對(duì)于所有的正整數(shù)都成立。
對(duì)于那些不成立的數(shù)所構(gòu)成的集合S，其中必定有一個(gè)最小的元素k。（1是不屬于集合S的，所以）
k已經(jīng)是集合S中的最小元素了，所以是不屬于S，這意味著對(duì)于命題而言是成立的——既然對(duì)于成立，那么也對(duì)k也應(yīng)該成立，這與我們完成的第二步驟矛盾。所以這個(gè)完成兩個(gè)步驟的命題能夠?qū)λ衝都成立。
注意到有些其它的公理確實(shí)是數(shù)學(xué)歸納法原理的可選的公理化形式。更確切地說(shuō)，兩者是等價(jià)的。
變體
在應(yīng)用，數(shù)學(xué)歸納法常常需要采取一些變化來(lái)適應(yīng)實(shí)際的需求。下面介紹一些常見(jiàn)的數(shù)學(xué)歸納法變體。
從0以外的數(shù)字開(kāi)始
如果我們想證明的命題并不是針對(duì)全部自然數(shù)，而只是針對(duì)所有大于等于某個(gè)數(shù)字b的自然數(shù)，那么證明的步驟需要做如下修改：
第一步，證明當(dāng)時(shí)命題成立。第二步，證明如果成立，那么可以推導(dǎo)出也成立。
用這個(gè)方法可以證明諸如“當(dāng)時(shí)，”這一類(lèi)命題。
針對(duì)偶數(shù)或奇數(shù)
如果我們想證明的命題并不是針對(duì)全部自然數(shù)，而只是針對(duì)所有奇數(shù)或偶數(shù)，那么證明的步驟需要做如下修改：
奇數(shù)方面：
第一步，證明當(dāng)時(shí)命題成立。第二步，證明如果成立，那么可以推導(dǎo)出也成立。
偶數(shù)方面：
第一步，證明當(dāng)或2時(shí)命題成立。第二步，證明如果成立，那么可以推導(dǎo)出也成立。
遞降歸納法（又稱(chēng)遞歸歸納法）
數(shù)學(xué)歸納法并不是只能應(yīng)用于形如“對(duì)任意的n”這樣的命題。對(duì)于形如“對(duì)任意的”這樣的命題，如果對(duì)一般的n比較復(fù)雜，而比較容易驗(yàn)證，并且我們可以實(shí)現(xiàn)從k到的遞推，的話，我們就能應(yīng)用歸納法得到對(duì)于任意的，原命題均成立。如果命題P(n)在時(shí)成立，并且對(duì)于任意自然數(shù)k，由成立，其中t是一個(gè)常量，那么P(n)對(duì)于一切自然數(shù)都成立.
跳躍歸納法
設(shè)P(n)表示一個(gè)與自然數(shù)n有關(guān)的命題，若(1)P(1)，P(2),…,P(l)成立;(2)假設(shè)P(k)成立，可以推出成立，則P(n)對(duì)一切自然數(shù)n都成立.
第一數(shù)學(xué)歸納法
一般地，證明一個(gè)與自然數(shù)n有關(guān)的命題P(n)，有如下步驟：
（1）證明當(dāng)n取第一個(gè)值n0時(shí)命題成立。對(duì)于一般數(shù)列取值為0或1，但也有特殊情況；
（2）假設(shè)當(dāng)（，k為自然數(shù)）時(shí)命題成立，證明當(dāng)時(shí)命題也成立。
綜合（1）（2），對(duì)一切自然數(shù)，命題P(n)都成立。
第二數(shù)學(xué)歸納法（完整歸納法）
另一個(gè)一般化的方法叫完整歸納法（也稱(chēng)第二數(shù)學(xué)歸納法），在第二步中我們假定式子不僅當(dāng)時(shí)成立，當(dāng)n小于或等于m時(shí)也成立。這樣可以設(shè)計(jì)出這樣兩步:
則命題成立。
例如，這種方法被用來(lái)證明：
其中fib(n)?是第n個(gè)斐波那契數(shù)和。 (即黃金分割)。如果我們可以假設(shè)式子已經(jīng)在當(dāng)和時(shí)成立，從之后可以直截了當(dāng)?shù)刈C明當(dāng)時(shí)式子成立。
這種方法也是第一種形式的特殊化：
結(jié)論：P(n)對(duì)一切自然數(shù)n成立。
倒推歸納法
又名反向歸納法
（1）驗(yàn)證對(duì)于無(wú)窮多個(gè)自然數(shù)n命題P(n)成立（無(wú)窮多個(gè)自然數(shù)可以是一個(gè)無(wú)窮數(shù)列中的數(shù)，如對(duì)于算術(shù)幾何不等式的證明，可以是，）；
（2）假設(shè)成立，并在此基礎(chǔ)上，推出P(k)成立，
綜合（1）（2），對(duì)一切自然數(shù)，命題P(n)都成立；
螺旋式歸納法
對(duì)兩個(gè)與自然數(shù)有關(guān)的命題P(n)，Q(n)，
（1）驗(yàn)證時(shí)P(n)成立；
（2）假設(shè)成立，能推出Q(k）成立，假設(shè) Q(k)成立，能推出 成立；
綜合（1）（2），對(duì)一切自然數(shù)，P(n)，Q(n)都成立。
發(fā)展歷程
已知最早的使用數(shù)學(xué)歸納法的證明出現(xiàn)于Francesco Maurolico的Arithmeticorum libri duo（1575年）。Maurolico利用遞推關(guān)系巧妙地證明出前n個(gè)奇數(shù)的總和是，由此總結(jié)出了數(shù)學(xué)歸納法。
最簡(jiǎn)單和常見(jiàn)的數(shù)學(xué)歸納法證明方法是證明當(dāng)n屬于所有正整數(shù)時(shí)一個(gè)表達(dá)式成立，這種方法是由下面兩步組成：
遞推的基礎(chǔ)：證明當(dāng)時(shí)表達(dá)式成立。
遞推的依據(jù)：證明如果當(dāng)時(shí)成立，那么當(dāng)時(shí)同樣成立。
這種方法的原理在于第一步證明起始值在表達(dá)式中是成立的，然后證明一個(gè)值到下一個(gè)值的證明過(guò)程是有效的。如果這兩步都被證明了，那么任何一個(gè)值的證明都可以被包含在重復(fù)不斷進(jìn)行的過(guò)程中。
參考資料 >
數(shù)學(xué)中的相鄰思想為何如此重要？.澎湃新聞·澎湃號(hào)·政務(wù).2024-01-20
費(fèi)馬猜想真有簡(jiǎn)潔證明： 本原解化約律和冪尾數(shù)周期律.澎湃新聞·澎湃號(hào)·政務(wù).2024-01-20