數學歸納法

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

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

定義

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

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

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

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

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

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

例子

例子1

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

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

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

證明

第一步-起始步驟

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

第二步-推遞步驟

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

假設${\displaystyle n=m}$時公式成立。即

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

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

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

${\displaystyle ={\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}}.}$

也就是說

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

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

解釋

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

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

例子2

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

證明

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

數學歸納法的變體

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

從0以外的自然數開始

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

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

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

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

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

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

只針對偶數或只針對奇數

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

奇數方面：

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

偶數方面：

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

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

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

遞迴歸納法

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

完整歸納法

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

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

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

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

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

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

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

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

超限歸納法

主條目：超限歸納法

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

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

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

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

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

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

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

形式寫法

使用二階邏輯

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

${\displaystyle \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 )}}$，

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

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

使用一階邏輯

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

${\displaystyle \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 \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 \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)，且所得之自然數模型無限大。根據勒文海姆-斯科倫定理，用一階邏輯表達的理論若有可數無限大的模型，則其有不可數大的模型，是故無法前頭將所述的模型公設化^[4]。亦即，用二階邏輯表達的公設僅允許一群模型彼此同構，而一階邏輯模型則因前述定理，並非每個模型都同構。

使用一階ZFC集合論

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

${\displaystyle \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 )}}$

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

數學歸納法的合理性

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

參見

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

參考文獻

1. Suber, Peter. Mathematical Induction. Earlham College. [2011-03-26]. （原始內容存檔於2011-05-24） （英語）.
2. Matt DeVos. Mathematical Induction (PDF). 西門菲莎大學 （英語）.
3. Gerardo con Diaz. Mathematical Induction (PDF). 哈佛大學. [2019-02-10]. （原始內容 (PDF)存檔於2013-05-02） （英語）.
4. Derek Goldrei. Propositional and predicate calculus: a model of argument. Springer-Verlag London. 2005: 286-287. ISBN 1-85233-921-7 （英語）.
5. Well Ordering Principle and the Principle of Mathematical Induction (PDF). [2019-02-03]. （原始內容 (PDF)存檔於2017-11-19） （英語）.

外部連結

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