基本介紹
- 中文名：數學歸納法
- 外文名：mathematical induction
- 類別：證明方法
- 適用範圍：數學
- 屬於：演繹推理法
- 原理：自然數公理
簡介,解題,原理,解題要點,合理性,變體,發展歷程,
簡介
數學歸納法（Mathematical Induction, MI）是一種數學證明方法，通常被用於證明某個給定命題在整個（或者局部）自然數範圍內成立。除了自然數以外，廣義上的數學歸納法也可以用於證明一般良基結構，例如：集合論中的樹。這種廣義的數學歸納法套用於數學邏輯和計算機科學領域，稱作結構歸納法。
在數論中，數學歸納法是以一種不同的方式來證明任意一個給定的情形都是正確的（第一個,第二個，第三個，一直下去概不例外）的數學定理。
雖然數學歸納法名字中有“歸納”，但是數學歸納法並非不嚴謹的歸納推理法，它屬於完全嚴謹的演繹推理法。事實上，所有數學證明都是演繹法。
解題
原理
最簡單和常見的數學歸納法是證明當n等於任意一個自然數時某命題成立。證明分下面兩步：
- 證明當n= 1時命題成立。
- 假設n=m時命題成立，那么可以推導出在n=m+1時命題也成立。（m代表任意自然數）
這種方法的原理在於：首先證明在某個起點值時命題成立，然後證明從一個值到下一個值的過程有效。當這兩點都已經證明，那么任意值都可以通過反覆使用這個方法推導出來。把這個方法想成多米諾效應也許更容易理解一些。例如：你有一列很長的直立著的多米諾骨牌，如果你可以：
- 證明第一張骨牌會倒。
- 證明只要任意一張骨牌倒了，那么與其相鄰的下一張骨牌也會倒。
骨牌一個接一個倒下就如同一個值接下一個值那么便可以下結論：所有的骨牌都會倒下。
解題要點
數學歸納法對解題的形式要求嚴格，數學歸納法解題過程中，
第一步：驗證n取第一個自然數時成立
第二步：假設n=k時成立，然後以驗證的條件和假設的條件作為論證的依據進行推導，在接下來的推導過程中不能直接將n=k+1代入假設的原式中去。
最後一步總結表述。
需要強調是數學歸納法的兩步都很重要，缺一不可，否則可能得到下面的荒謬證明：
證明1：所有的馬都是一種顏色
首先，第一步，這個命題對n=1時成立，即，只有1匹馬時，馬的顏色只有一種。
第二步，假設這個命題對n成立，即假設任何n匹馬都是一種顏色。那么當我們有n+1匹馬時，不妨把它們編好號：
1, 2, 3……n, n+1
對其中（1、2……n）這些馬，由我們的假設可以得到，它們都是同一種顏色；
對（2、3……n、n+1）這些馬，我們也可以得到它們是一種顏色；
由於這兩組中都有（2、3、……n）這些馬，所以可以得到，這n+1種馬都是同一種顏色。
這個證明的錯誤來於推理的第二步：當n=1時，n+1=2，此時馬的編號只有1、2，那么分的兩組是（1）和（2）——它們沒有交集，所以第二步的推論是錯誤的。數學歸納法第二步要求n→n+1過程對n=1，2，3……的數都成立，而上面的證明就好比多米諾骨牌的第一塊和第二塊之間間隔太大，推倒了第一塊，但它不會推倒第二塊。即使我們知道第二塊倒下會推倒第三塊等等，但這個過程早已在第一和第二塊之間就中斷了。
證明2：舉例證明下面的定理
第一步，驗證該公式在 n = 1 時成立。即有左邊=1，右邊=
=1，所以這個公式在n = 1時成立。
第二步，需要證明假設n = m 時公式成立，那么可以推導出n = m+1 時公式也成立。步驟如下：
假設n = m 時公式成立，即
（等式1）
然後在等式兩邊同時分別加上m + 1 得到
（等式2）
這就是n = m+1 時的等式。我們下一步需要根據 等式1證明 等式2 成立。通過因式分解合併，等式2的右邊
也就是
這樣我們就完成了由n=m成立推導出n=m+1成立的過程，證畢。
結論：對於任意自然數n，公式均成立。
對於以上例2的分析
在這個證明中，歸納的過程如下：
- 首先證明n=1成立。
- 然後證明從n=m 成立可以推導出n=m+1 也成立（這裡實際套用的是演繹推理）。
- 根據上兩條從n=1 成立可以推導出n=1+1，也就是n=2 成立。
- 繼續推導，可以知道n=3 成立。
- 從 n=3 成立可以推導出n=4 也成立……
- 不斷重複3的推導過程（這就是所謂“歸納”推理的地方）。
- 我們便可以下結論：對於任意非零自然數n，公式成立。
合理性
數學歸納法的原理，通常被規定作為自然數公理（參見皮亞諾公理）。但是在另一些公理的基礎上，它可以用一些邏輯方法證明。數學歸納法原理可以由下面的良序性質（最小自然數原理）公理可以推出：
自然數集是良序的。（每個非空的正整數集合都有一個最小的元素）
比如{1, 2, 3 , 4, 5}這個正整數集合中有最小的數——1.
下面我們將通過這個性質來證明數學歸納法：
對於一個已經完成上述兩步證明的數學命題，我們假設它並不是對於所有的正整數都成立。
對於那些不成立的數所構成的集合S，其中必定有一個最小的元素k。（1是不屬於集合S的，所以k>1）
k已經是集合S中的最小元素了，所以k-1是不屬於S，這意味著k-1對於命題而言是成立的——既然對於k-1成立，那么也對k也應該成立，這與我們完成的第二步驟矛盾。所以這個完成兩個步驟的命題能夠對所有n都成立。
注意到有些其它的公理確實是數學歸納法原理的可選的公理化形式。更確切地說，兩者是等價的。
變體
在套用，數學歸納法常常需要採取一些變化來適應實際的需求。下面介紹一些常見的數學歸納法變體。
從0以外的數字開始
如果我們想證明的命題並不是針對全部自然數，而只是針對所有大於等於某個數字b的自然數，那么證明的步驟需要做如下修改：
第一步，證明當n=b時命題成立。第二步，證明如果n=m(m≥b）成立，那么可以推導出n=m+1也成立。
用這個方法可以證明諸如“當n≥3時，n^2>2n”這一類命題。
針對偶數或奇數
如果我們想證明的命題並不是針對全部自然數，而只是針對所有奇數或偶數，那么證明的步驟需要做如下修改：
奇數方面：
第一步，證明當n=1時命題成立。第二步，證明如果n=m成立，那么可以推導出n=m+2也成立。
偶數方面：
第一步，證明當n=0或2時命題成立。第二步，證明如果n=m成立，那么可以推導出n=m+2也成立。
遞降歸納法（又稱遞歸歸納法）
數學歸納法並不是只能套用於形如“對任意的n”這樣的命題。對於形如“對任意的n=0,1,2,...,m”這樣的命題，如果對一般的n比較複雜，而n=m比較容易驗證，並且我們可以實現從k到k-1的遞推，k=1,...,m的話，我們就能套用歸納法得到對於任意的n=0,1,2,...,m，原命題均成立。如果命題P(n）在n=1,2,3,......,t時成立，並且對於任意自然數k，由P(k),P(k+1）,P(k+2）,......,P(k+t-1）成立，其中t是一個常量，那么P(n）對於一切自然數都成立.
跳躍歸納法
設P(n)表示一個與自然數n有關的命題，若(1)P(1)，P(2),…,P(l)成立;(2)假設P(k)成立，可以推出P (k+l)成立,則P(n)對一切自然數n都成立.
第一數學歸納法
一般地，證明一個與自然數n有關的命題P(n），有如下步驟：
（1）證明當n取第一個值n0時命題成立。n0對於一般數列取值為0或1，但也有特殊情況；
（2）假設當n=k（k≥n0，k為自然數）時命題成立，證明當n=k+1時命題也成立。
綜合（1）（2），對一切自然數n（≥n0），命題P(n）都成立。
第二數學歸納法（完整歸納法）
另一個一般化的方法叫完整歸納法（也稱第二數學歸納法），在第二步中我們假定式子不僅當n=m時成立，當n小於或等於m時也成立.這樣可以設計出這樣兩步:
- 證明當n= 0時式子成立.
- 假設當n≤m時成立，證明當n=m+ 1時式子也成立.
則命題成立。
例如，這種方法被用來證明：
其中fib（n） 是第n個斐波納契數和Φ =(√5+1） / 2。1/Φ =(√5－1） / 2 (即黃金分割)。如果我們可以假設式子已經在當n=m和n=m− 1時成立，從fib（m+ 1） =fib(m) +fib（m− 1）之後可以直截了當地證明當n=m+ 1時式子成立。
這種方法也是第一種形式的特殊化：
- 定義P（n） 是我們將證的式子,
- P（0）和P（1）成立
- P（m+ 1）在P（m）和P（m− 1）成立時成立。
結論：P（n）對一切自然數n成立。
倒推歸納法
又名反向歸納法
（1）驗證對於無窮多個自然數n命題P(n）成立（無窮多個自然數可以是一個無窮數列中的數，如對於算術幾何不等式的證明，可以是2^k，k≥1）；
（2）假設P(k+1）（k≥n0）成立，並在此基礎上，推出P(k）成立，
綜合（1）（2），對一切自然數n（≥n0），命題P(n）都成立；
螺旋式歸納法
對兩個與自然數有關的命題P(n），Q(n），
（1）驗證n=n0時P(n）成立；
（2）假設P(k）（k>n0）成立，能推出Q(k）成立，假設 Q(k）成立，能推出 P(k+1）成立；
綜合（1）（2），對一切自然數n（≥n0），P(n），Q(n）都成立。
發展歷程
已知最早的使用數學歸納法的證明出現於Francesco Maurolico的Arithmeticorum libri duo（1575年）。Maurolico利用遞推關係巧妙地證明出前n個奇數的總和是n^2，由此總結出了數學歸納法。
最簡單和常見的數學歸納法證明方法是證明當n屬於所有正整數時一個表達式成立，這種方法是由下面兩步組成：
遞推的基礎：證明當n=1時表達式成立。
遞推的依據：證明如果當n=m時成立，那么當n=m+1時同樣成立。
這種方法的原理在於第一步證明起始值在表達式中是成立的，然後證明一個值到下一個值的證明過程是有效的。如果這兩步都被證明了，那么任何一個值的證明都可以被包含在重複不斷進行的過程中。
