數學歸納法

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

雖然數學歸納法名字中有「歸納」，但是數學歸納法並不是不嚴謹的歸納推理法，它是屬於完全嚴謹的演繹推理法。

定義

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

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

1. 證明當 n = 1 時命題成立。
2. 證明如果在 n = m 時命題成立，那麼可以推導出在 n = m+1 時命題也成立。（m 代表任意自然數）

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

1. 證明第一張骨牌會倒。
2. 證明只要任意一張骨牌倒了，那麼與其相鄰的下一張骨牌也會倒。

那麼便可以下結論：所有的骨牌都會倒。

例子

假設我們要證明下面這個公式（命題）：

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

其中 n 為任意自然數。這是用於計算前 n 個自然數的和的簡單公式。證明這個公式成立的步驟如下。

證明

第一步

第一步是驗證這個公式在 n = 1 時成立。我們有左邊 = 1，而右邊 = 1(1 + 1) / 2 = 1，所以這個公式在 n = 1 時成立。第一步完成。

第二步

第二步我們需要證明如果假設 n = m 時公式成立，那麼可以推導出 n = m+1 時公式也成立。證明步驟如下。

我們先假設 n = m 時公式成立。即

$1 + 2 + \cdots + m = \frac{m(m + 1)}{2}$ （等式 1）

然後在等式等號兩邊分別加上 m + 1 得到

$1 + 2 + \cdots + m + (m + 1) = \frac{m(m + 1)}{2} + (m+ 1)$ （等式 2）

這就是 n = m+1 時的等式。我們現在需要根據等式 1 證明等式 2 成立。通過因式分解合併，等式 2 的右手邊

$= \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) 也成立。（這裡實際應用的是演繹推理法）
3. 根據上兩條從 P(1) 成立可以推導出 P(1+1)，也就是 P(2) 成立。
4. 繼續推導，可以知道 P(3)成立。
5. 從 P(3) 成立可以推導出 P(4) 也成立。
6. 不斷重複推導下一命題成立的步驟。（這就是所謂「歸納」推理的地方）
7. 我們便可以下結論：對於任意自然數 n，P(n) 成立。

數學歸納法的變體

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

從 0 以外的自然數開始

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

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

用這個方法可以證明諸如「當 n ≥ 3 時，n² > 2n」這一類命題。

只針對偶數或只針對奇數

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

奇數方面：

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

偶數方面：

1. 第一步，證明當 n = 0或2 時命題成立。
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，原命題均成立。

完整歸納法

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

1. 證明當n = 0時式子成立.
2. 證明當 n ≤ m 時成立，那麼當n = m + 1時式子也成立.

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

fib(n) = [Φⁿ − (−1/Φ)ⁿ ] / 5^1/2

fib(n) 是第n個斐波納契數 和 Φ = (1 + 5^1/2) / 2 (即黃金分割). 如果我們可以假設式子已經在當 n = m 和 n = m − 1時成立，從 fib(m + 1) = fib(m) + fib(m − 1)之後可以直截了當地證明當n=m + 1 時式子成立.

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

1. 定義 P(n) 是我們將證的式子,
2. P(0)和P(1)成立
3. P(m + 1)在P(m)和P(m − 1)成立時成立。

結論：P(n)對一切自然數n成立。

超限歸納法

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

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

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

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

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

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

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

數學歸納法的合理性

數學歸納法的原理作為自然數公理，通常是被規定了的（參見皮亞諾公理）。但是它可以用一些邏輯方法證明。比如，如果公理「自然數集是良序的」被使用。

注意到有些其他的公理確實的是數學歸納法原理中的二者擇一的公式化。更確切地說，兩個都是等價的。參見數學歸納法的證明。

相關條目

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

外部連結

• Mathematical Induction, Examples（英文）