數學歸納法

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

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

## 定義

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

<image>

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

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

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

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

## 例子

### 例子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)$均成立。

#### 解釋

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

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

## 數學歸納法的變體

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

### 從自然數開始

第一種情況：

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

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

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

第二種情況：

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

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

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

### 只針對偶數或只針對奇數

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

奇數方面：

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

偶數方面：

- 第一步，證明當$n=0$或$n = 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$時也成立。這樣可以設計出這樣兩步:

- 證明當$n=0$時式子成立.
- 證明當$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$時式子成立.

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

- 定義$\mathrm{P}(n)$是我們將證的式子,
- $\mathrm{P}(0)$和$\mathrm{P}(1)$成立
- $\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$）。

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

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

- $m$是一個極小元素，也就是沒有一個元素小於$m$
- $m$有一個直接的前輩，比$m$小的元素有一個大的元素
- $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