数学归纳法

**數學歸納法**（英語：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$ 或 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$_ 成立。

### 超限歸納法

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

1. 證明如果式子在所有的 $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 集合論直接定義自然數，使得歸納法本身是定理而非公設。

## 數學歸納法的合理性

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

## 參見

* 歸納推理
* 演繹推理
* 結構歸納法

## 參考文獻

## 外部連結

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