數學歸納法

數學歸納法（英語：mathematical induction，縮寫：MI）是一種數學證明方法，通常被用於證明某個給定命題在整個或者局部自然數範圍內成立。除了自然數以外，廣義上的數學歸納法也可以用於證明一般良基結構，例如：集合論中的樹。這種廣義的數學歸納法應用於數學邏輯和計算機科學領域，稱作結構歸納法。

雖然數學歸納法名字中有「歸納」，但是數學歸納法並非邏輯上不嚴謹的歸納推理法，它屬於完全嚴謹的演繹推理法。事實上，所有數學證明都屬於演繹推理方法。

定義

最簡單和常見的數學歸納法是證明當$n$等於任意一個自然數時某命題成立。證明分下面兩步：

骨牌一個接一個倒下，就如同一個值到下一個值的過程

1. 證明 「當$n=1$時命題成立。」（選擇數字1因其作為自然數集合中的最小值）
2. 證明 「若假設在$n=m$時命題成立，可推導出在$n=m 1$時命題成立。（$m$代表任意自然數）」

這種方法的原理在於：首先證明在某個起點值時命題成立，然後證明從一個值到下一個值的過程有效。當這兩點都已經證明，那麼任意值都可以通過反覆使用這個方法推導出來。把這個方法想成多米諾骨牌效應也許更容易理解一些。例如：你有一列很長的直立着的多米諾骨牌，如果你可以：

1. 證明 「第一張骨牌會倒。」
2. 證明 「只要任意一張骨牌倒了，其下一張骨牌也會因為前面的骨牌倒而跟著倒。」

則可下結論：所有的骨牌都會倒下。

例子

例子1

證明下面這個給定公式（命題）為真：

$1 2 3 \cdots n={\frac {n(n 1)}{2}}$

其中$n$為任意自然數。這是用於計算前n個自然數的和的簡單公式。

證明

第一步-起始步驟

第一步是驗證這個公式在$n=1$時成立。左邊$=1$，而右邊$={\frac {1(1 1)}{2}}=1$，所以這個公式在$n=1$時成立。第一步完成。

第二步-推遞步驟

第二步證明假設$n=m$時公式成立，則可推理出$n=m 1$時公式也成立。 證明步驟如下。

假設$n=m$時公式成立。即

$1 2 \cdots m={\frac {m(m 1)}{2}}$【等式$P(m)$】

然後在等式等號兩邊分別加上$m 1$得到 $1 2 \cdots m (m 1)={\frac {m(m 1)}{2}} (m 1)$【等式$P(m 1)$】 這就是$n=m 1$時的等式。

現在需要根據等式等式$P(m 1)$演繹出等式$P(m)$的符號形式。（需要注意的是如果給定公式不為真，則做不到）通過因式分解合併(形式變換/字符操縱)，等式$P(m 1)$的右手邊

$={\frac {m(m 1)}{2}} {\frac {2(m 1)}{2}}={\frac {(m 2)(m 1)}{2}}={\frac {(m 1)(m 2)}{2}}={\frac {(m 1)[(m 1) 1]}{2}}.$

也就是說

$1 2 \cdots (m 1)={\frac {(m 1)[(m 1) 1]}{2}}$

這樣便證明了從等式$P(m)$成立可推理出等式$P(m 1)$也成立。證明至此完成，結論：對於任意自然數$n$，$P(n)$均成立。

解釋

在這個證明中，推理的過程如下：

1. 首先證明命題$P(1)$成立，即公式在$n=1$時成立。
2. 然後證明從命題$P(m)$成立可以推演出命題$P(m 1)$也成立。【此部實際屬於演繹推理法。技術方法是基於命題$P(m 1)$的符號形式變換出命題$P(m)$的符號形式。】
3. 根據上兩條從命題$P(1)$成立可以推理出命題$P(1 1)$，也就是命題$P(2)$成立。
4. 繼續推理，可以知道命題$P(3)$成立。
5. 從命題$P(3)$成立可以推導出命題$P(4)$也成立。
6. 不斷的重複推導下一命題成立的步驟。（這就是所謂「歸納」推理的地方）
7. 我們便可以下結論：對於任意自然數$n$，命題$P(n)$ 成立。

例子2

證明對於Fibonacci數列，定義$F_{n}=F_{n-1} F_{n-2}$，且$F_{0}=0,F_{1}=1$，則$F_{0} F_{1} F_{2} \cdots F_{n}=F_{n 2}-1$。

證明

首先，我們先使得$n=0$的情況成立，$F_{0}=F_{2}-1,0=1-1=0$ 然後，我們假定$n=k$的情況下的成立的，$F_{0} F_{1} ... F_{k}=F_{k 2}-1$ 然後我們使得$n=k 1$的情況也成立，（這是為了表明，如果有任意數k使得其成立，則有其 1也成立） $F_{0} F_{1} ... F_{k} F_{k 1}=F_{k 2}-1 F_{k 1}=F_{k 3}-1$ 於是我們得證，即從$n=0$，到$n=0 1,1 1,2 1$到所有正實數都成立，就像多米諾骨牌的第一塊$n=0$成立而且每一塊的下一塊都成立（$k,k 1$)

數學歸納法的變體

在應用中，數學歸納法常常需要採取一些變化來適應實際的需求。下面介紹一些常見的數學歸納法變體。

從0以外的自然數開始

第一種情況： 如果欲證明的命題並不是針對全部自然數，而只是針對所有大於等於某個數字b的自然數，那麼證明的步驟需要做如下修改：

1. 第一步，證明當$n=b$時命題成立。
2. 第二步，證明如果$n=m$（$m\geq b$） 成立，那麼可以推導出$n=m 1$也成立。

用這個方法可以證明諸如「當$n\geq 5$時，$2^{n}>n^{2}$這一類命題。

第二種情況： 如果欲證明的命題針對全部自然數，但僅當大於等於某個數字b時比較容易證明，則可參考如下步驟：

1. 第一步，證明當$n=0,1,2,\cdots ,b$時命題成立。
2. 第二步，證明如果$n=m$（$m\geq b$）成立，那麼可以推導出$n=m 1$也成立。

用這種方法可以證明一些需要通過放縮來證明的不等式。

只針對偶數或只針對奇數

如果我們想證明的命題並不是針對全部自然數，而只是針對所有奇數或偶數，那麼證明的步驟需要做如下修改：

奇數方面：

1. 第一步，證明當$n=1$時命題成立。
2. 第二步，證明如果$n=m$成立，那麼可以推導出$n=m 2$也成立。

偶數方面：

1. 第一步，證明當$n=0$或$n=2$時命題成立。
2. 第二步，證明如果$n=m$成立，那麼可以推導出$n=m 2$也成立。

或調整命題表述，使之變為對所有正整數成立，例如

證明「$1 3 5 7 \cdots a={\frac {(a 1)^{2}}{4}}$對所有正奇數$a$成立」等價於證明「$1 3 5 7 \cdots (2b-1)=b^{2}$對所有正整數$b$成立」。

遞迴歸納法

又名遞降歸納法。數學歸納法並不是只能應用於形如「對任意的$n$」這樣的命題。對於形如「對任意的$n=0,1,2,\cdots ,m$」這樣的命題，如果對一般的$n$比較複雜，而$n=m$比較容易驗證，並且我們可以實現從$k$到$k-1$的遞推，$k=1,\cdots ,m$的話，我們就能應用歸納法得到對於任意的$n=0,1,2,\cdots ,m$，原命題均成立。

完整歸納法

另一個一般化的方法叫完整歸納法（也稱第二數學歸納法或強歸納法），在第二步中我們假定式子不僅當$n=m$時成立，當$n$小於或等於$m$時也成立。這樣可以設計出這樣兩步:

1. 證明當$n=0$時式子成立.
2. 證明當$n\leq m$時成立，那麼當$n=m 1$時式子也成立.

例如，這種方法被用來證明：

$\mathrm {fib} (n)={\frac {\Phi ^{n}-\left(-\Phi \right)^{-n}}{5^{\frac {1}{2}}}}$

其中 $\mathrm {fib} (n)$是第$n$個斐波納契數和$\Phi ={\frac {1 5^{\frac {1}{2}}}{2}}$（即黃金分割）。如果我們可以假設式子已經在當$n=m$和$n=m-1$時成立，從$\mathrm {fib} (m 1)=\mathrm {fib} (m) \mathrm {fib} (m-1)$之後可以直截了當地證明當$n=m 1$時式子成立.

這種方法也是第一種形式的特殊化：

1. 定義$\mathrm {P} (n)$是我們將證的式子,
2. $\mathrm {P} (0)$和$\mathrm {P} (1)$成立
3. $\mathrm {P} (m 1)$在$\mathrm {P} (m)$和$\mathrm {P} (m-1)$成立時成立。

結論：$\mathrm {P} (n)$對一切自然數$n$成立。

超限歸納法

主條目：超限歸納法

最後兩步可以用這樣一步表示：

證明如果式子在所有的$n<m$成立，那麼式子在當$n=m$時也成立。

實際上這是數學歸納法的大多數通式，可以知道他不僅對表達自然數的式子有效，而且對於任何在良基集（也就是一個偏序的集合，包括有限降鏈）中元素的式子也有效（這裡"$<$"被定義為$a<b$ 當且僅當$a\leq b$和$a\neq b$）。

這種形式的歸納法當運用到序數（以良序的和一些的良基類的形式）時被稱為超限歸納法，它在集合論、拓撲學和其他領域是一種重要的方法。

要區別用超限歸納法證明的命題的三種情況：

1. $m$是一個極小元素，也就是沒有一個元素小於$m$
2. $m$有一個直接的前輩，比$m$小的元素有一個大的元素
3. $m$沒有任何前輩，也就是$m$是一個界限序數.

參見數學歸納法的三種形式。

形式寫法

使用二階邏輯

二階邏輯可捕捉數學歸納法這概念，表達成如下邏輯式：

$\displaystyle \forall P{\Bigl (}P(0)\land \forall k{\bigl (}P(k)\Rightarrow P(k 1){\bigr )}\Rightarrow \forall n{\bigl (}P(n){\bigr )}{\Bigr )}$，

$P(.)$是容納一自然數的述詞變元，遍歷所有述詞而非個別數字，為二階量詞（是故此式與二階邏輯有關），$k$與$n$則是自然數變元，遍歷所有自然數。

白話解釋此式，此式說：起始步驟$P(0)$與推遞步驟（即歸納假設，$P(k)$蘊涵 $P(k 1)$） 兩步成立會導出對任一自然數$n$， $P(n)$成立之結論。通常，我們為了證明第二步，會假設$P(n)$成立（歸納假設），再進一步證明$P(n 1)$。此牽涉到條件證法，將條件句之前件作為假設，假定其正確以便於證明。

使用一階邏輯

若用一階邏輯將數學歸納法公設化，則須採用公設模式，替每一個可能存在的述詞設下針對其的獨立公設。舉例而言，我們僅允許三個一階述詞存在，分別名為$P_{1}$、$P_{2}$、$P_{3}$ ，則原先以二階邏輯描述的公設可改寫為：

$\displaystyle P_{1}(0)\land \forall k{\bigl (}P_{1}(k)\to P_{1}(k 1){\bigr )}\to \forall n{\bigl (}P_{1}(n){\bigr )}$，

$\displaystyle P_{2}(0)\land \forall k{\bigl (}P_{2}(k)\to P_{2}(k 1){\bigr )}\to \forall n{\bigl (}P_{2}(n){\bigr )}$，

$\displaystyle P_{3}(0)\land \forall k{\bigl (}P_{3}(k)\to P_{3}(k 1){\bigr )}\to \forall n{\bigl (}P_{3}(n){\bigr )}$，

。然而其強度與以二階邏輯描述之邏輯式不同，前者較後者弱。理由為一階邏輯述詞之數量為可數，而二階邏輯量限所迭代的集合為不可數。

此外，二階邏輯所表示的歸納公設綜合其它皮亞諾公設為同疇(categorical)，且所得之自然數模型無限大。根據勒文海姆-斯科倫定理，用一階邏輯表達的理論若有可數無限大的模型，則其有不可數大的模型，是故無法前頭將所述的模型公設化。亦即，用二階邏輯表達的公設僅允許一群模型彼此同構，而一階邏輯模型則因前述定理，並非每個模型都同構。

使用一階ZFC集合論

一階ZFC集合論不允許述詞被遍歷， 但我們可以藉由遍歷集合，繞過一階邏輯之限制，描述歸納法：

$\forall A{\Bigl (}0\in A\land \forall k\in \mathbb {N} {\bigl (}k\in A\to (k 1)\in A{\bigr )}\to \mathbb {N} \subseteq A{\Bigr )}$

$A$ 本身是集合，但可視作命題——只要命題在這數下成立，數字就會收入集合。別於皮亞諾公設，將數學歸納法定為公設，ZFC集合論直接定義自然數，使得歸納法本身是定理而非公設。

數學歸納法的合理性

皮亞諾公理視數學歸納法不證自明，設作公理，而於策梅洛-弗蘭克爾集合論，數學歸納法可從良序定理推導出來。 需要注意的是數學歸納法只能判定給定命題的真，而不能證偽，因為在形式變換這一過程需要一定技巧與靈感。抽象的概念如自然數，可通過抽象的工具去處理。通過有限的步驟處理無限的對象如證明質數的無窮。

參見

• 歸納推理
• 演繹推理
• 結構歸納法
• 完整歸納法

外部連結

• Mathematical Induction, Examples （頁面存檔備份，存於網際網路檔案館）（英文）