數學歸納法

維基百科,自由的百科全書
前往: 導覽搜尋

數學歸納法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,而右邊 =\frac{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 = mmb) 成立,那麼可以推導出n = m+1也成立。

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

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

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

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

只針對偶數或只針對奇數[編輯]

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

奇數方面:

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

偶數方面:

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

遞降歸納法 又名 遞迴歸納法[編輯]

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

完整歸納法[編輯]

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

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

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

fibn) = [Φn −(−1/Φ)n ] / 51/2

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

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

  1. 定義Pn) 是我們將證的式子,
  2. P0P1)成立
  3. Pm + 1)在Pm)和Pm − 1)成立時成立。

結論:Pn)對一切自然數n成立。

超限歸納法[編輯]

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

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

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

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

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

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

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

數學歸納法的合理性[編輯]

數學歸納法的原理作為自然數公理,通常是被規定了的(參見皮亞諾公理)。

相關條目[編輯]

外部連結[編輯]