數學歸納法(英語:Mathematical Induction,縮寫:MI)是一種數學證明方法,通常被用於證明某個給定命題在整個或者局部自然數範圍內成立。除了自然數以外,廣義上的數學歸納法也可以用於證明一般良基結構,例如:集合論中的樹。這種廣義的數學歸納法應用於數學邏輯和計算機科學領域,稱作結構歸納法。
雖然數學歸納法名字中有「歸納」,但是數學歸納法並非邏輯上不嚴謹的歸納推理法,它屬於完全嚴謹的演繹推理法。[1]事實上,所有數學證明都屬於演繹推理方法。
最簡單和常見的數學歸納法是證明當
等於任意一個自然數時某命題成立。證明分下面兩步:
骨牌一個接一個倒下,就如同一個值到下一個值的過程
- 證明 「當
時命題成立。」(選擇數字1因其作為自然數集合中的最小值)
- 證明 「若假設在
時命題成立,可推導出在
時命題成立。(
代表任意自然數)」
這種方法的原理在於:首先證明在某個起點值時命題成立,然後證明從一個值到下一個值的過程有效。當這兩點都已經證明,那麼任意值都可以通過反覆使用這個方法推導出來。把這個方法想成多米諾骨牌效應也許更容易理解一些。[2][3]例如:你有一列很長的直立著的多米諾骨牌,如果你可以:
- 證明 「第一張骨牌會倒。」
- 證明 「只要任意一張骨牌倒了,其下一張骨牌也會因為前面的骨牌倒而跟著倒。」
則可下結論:所有的骨牌都會倒下。
證明下面這個給定公式(命題)為真:
其中
為任意自然數。這是用於計算前n個自然數的和的簡單公式。
第一步是驗證這個公式在
時成立。左邊
,而右邊
,所以這個公式在
時成立。第一步完成。
第二步證明假設
時公式成立,則可推理出
時公式也成立。 證明步驟如下。
假設
時公式成立。即
【等式
】
然後在等式等號兩邊分別加上
得到
【等式
】
這就是
時的等式。
現在需要根據等式等式
演繹出等式
的符號形式。(需要注意的是如果給定公式不為真,則做不到)通過因式分解合併(形式轉換/字符操縱),等式
的右手邊
也就是說
這樣便證明了從等式
成立可推理出等式
也成立。證明至此完成,結論:對於任意自然數
,
均成立。
在這個證明中,推理的過程如下:
- 首先證明命題
成立,即公式在
時成立。
- 然後證明從命題
成立可以推演出命題
也成立。【此部實際屬於演繹推理法。技術方法是基於命題
的符號形式轉換出命題
的符號形式。】
- 根據上兩條從命題
成立可以推理出命題
,也就是命題
成立。
- 繼續推理,可以知道命題
成立。
- 從命題
成立可以推導出命題
也成立。
- 不斷的重複推導下一命題成立的步驟。(這就是所謂「歸納」推理的地方)
- 我們便可以下結論:對於任意自然數
,命題
成立。
證明對於Fibonacci數列,定義
,且
,則
。
首先,我們先使得
的情況成立,
然後,我們假定
的情況下的成立的,
然後我們使得
的情況也成立,(這是為了表明,如果有任意數k使得其成立,則有其+1也成立)
於是我們得證,即從
,到
到所有正實數都成立,就像多米諾骨牌的第一塊
成立而且每一塊的下一塊都成立(
)
在應用中,數學歸納法常常需要採取一些變化來適應實際的需求。下面介紹一些常見的數學歸納法變體。
第一種情況:
如果欲證明的命題並不是針對全部自然數,而只是針對所有大於等於某個數字b的自然數,那麼證明的步驟需要做如下修改:
- 第一步,證明當
時命題成立。
- 第二步,證明如果
(
) 成立,那麼可以推導出
也成立。
用這個方法可以證明諸如「當
時,
這一類命題。
第二種情況:
如果欲證明的命題針對全部自然數,但唯若大於等於某個數字b時比較容易證明,則可參考如下步驟:
- 第一步,證明當
時命題成立。
- 第二步,證明如果
(
)成立,那麼可以推導出
也成立。
用這種方法可以證明一些需要通過放縮來證明的不等式。
如果我們想證明的命題並不是針對全部自然數,而只是針對所有奇數或偶數,那麼證明的步驟需要做如下修改:
奇數方面:
- 第一步,證明當
時命題成立。
- 第二步,證明如果
成立,那麼可以推導出
也成立。
偶數方面:
- 第一步,證明當
或2時命題成立。
- 第二步,證明如果
成立,那麼可以推導出
也成立。
或調整命題表述,使之變為對所有正整數成立,例如
- 證明「
對所有正奇數
成立」等價於證明「
對所有正整數
成立」。
又名遞降歸納法。數學歸納法並不是只能應用於形如「對任意的
」這樣的命題。對於形如「對任意的
」這樣的命題,如果對一般的
比較複雜,而
比較容易驗證,並且我們可以實現從
到
的遞推,
的話,我們就能應用歸納法得到對於任意的
,原命題均成立。
另一個一般化的方法叫完整歸納法(也稱第二數學歸納法或強歸納法),在第二步中我們假定式子不僅當
時成立,當
小於或等於
時也成立。這樣可以設計出這樣兩步:
- 證明當
時式子成立.
- 證明當
時成立,那麼當
時式子也成立.
例如,這種方法被用來證明:
![{\displaystyle \mathrm {fib} (n)={\frac {\Phi ^{n}-\left(-\Phi \right)^{-n}}{5^{\frac {1}{2}}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/449fcf38d9abca2cb3cecdd4d6a5d62386d6ae2f)
其中
是第
個費波納契數和
(即黃金分割)。如果我們可以假設式子已經在當
和
時成立,從
之後可以直截了當地證明當
時式子成立.
這種方法也是第一種形式的特殊化:
- 定義
是我們將證的式子,
和
成立
在
和
成立時成立。
結論:
對一切自然數
成立。
最後兩步可以用這樣一步表示:
- 證明如果式子在所有的
成立,那麼式子在當
時也成立。
實際上這是數學歸納法的大多數通式,可以知道他不僅對表達自然數的式子有效,而且對於任何在良基集(也就是一個偏序的集合,包括有限降鏈)中元素的式子也有效(這裡"
"被定義為
若且唯若
和
)。
這種形式的歸納法當運用到序數(以良序的和一些的良基類的形式)時被稱為超限歸納法,它在集合論、拓撲學和其他領域是一種重要的方法。
要區別用超限歸納法證明的命題的三種情況:
是一個極小元素,也就是沒有一個元素小於![{\displaystyle m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
有一個直接的前輩,比
小的元素有一個大的元素
沒有任何前輩,也就是
是一個界限序數.
參見數學歸納法的三種形式。
二階邏輯可捕捉數學歸納法這概念,表達成如下邏輯式:
,
是容納一自然數的述詞變元,遍歷所有述詞而非個別數字,為二階量詞(是故此式與二階邏輯有關),
與
則是自然數變元,遍歷所有自然數。
白話解釋此式,此式說:起始步驟
與推遞步驟(即歸納假設,
蘊涵
) 兩步成立會導出對任一自然數
,
成立之結論。通常,我們為了證明第二步,會假設
成立(歸納假設),再進一步證明
。此牽涉到條件證法,將條件句之前件作為假設,假定其正確以便於證明。
若用一階邏輯將數學歸納法公設化,則須採用公設模式,替每一個可能存在的述詞設下針對其的獨立公設。舉例而言,我們僅允許三個一階述詞存在,分別名為
、
、
,則原先以二階邏輯描述的公設可改寫為:
,
,
,
。然而其強度與以二階邏輯描述之邏輯式不同,前者較後者弱。理由為一階邏輯述詞之數量為可數,而二階邏輯量限所迭代的集合為不可數。
此外,二階邏輯所表示的歸納公設綜合其它皮亞諾公設為同疇(categorical),且所得之自然數模型無限大。根據勒文海姆-斯科倫定理,用一階邏輯表達的理論若有可數無限大的模型,則其有不可數大的模型,是故無法前頭將所述的模型公設化[4]。亦即,用二階邏輯表達的公設僅允許一群模型彼此同構,而一階邏輯模型則因前述定理,並非每個模型都同構。
一階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 )}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4757318e068a3d55ce71fb1205b13ca936b2a392)
本身是集合,但可視作命題——只要命題在這數下成立,數字就會收入集合。別於皮亞諾公設,將數學歸納法定為公設,ZFC集合論直接定義自然數,使得歸納法本身是定理而非公設。
皮亞諾公理視數學歸納法不證自明,設作公理,而於策梅洛-弗蘭克爾集合論,數學歸納法可從良序定理推導出來。[5] 需要注意的是數學歸納法只能判定給定命題的真,而不能證偽,因為在形式轉換這一過程需要一定技巧與靈感。抽象的概念如自然數,可通過抽象的工具去處理。通過有限的步驟處理無限的物件如證明質數的無窮。