使用者討論:Dz902/沙盒/數學歸納法

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

需要留意的是,數學歸納法雖然名字中有「歸納」,但是實際上數學歸納法並不屬於不嚴謹歸納推理法,實際上是屬於完全嚴謹的演繹推理法

定義

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

 
骨牌一個接一個倒下,就如同一個值到下一個值的過程。
  1. 證明當 n = 0 時命題成立。
  2. 證明如果在 n = m 時命題成立,那麼可以推導出在 n = m+1 時命題也成立。(m 代表任意自然數)

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

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

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

例子

假設我們要證明下面這個公式(命題):

 

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

證明

第一步

第一步證明的是這個公式在 n = 0 時成立(即 P(0) 成立)。這裡要注意的是 0 = 0,而 0(0 + 1) / 2 = 0,所以這個公式在 n = 0 時成立。證明的第一步完成。

第二步

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

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

  (等式 1)

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

  (等式 2)

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

 

也就是說

 

這樣便證明了從 P(m) 成立可以推導出 P(m+1) 也成立。證明至此結束,結論:對於任意自然數 n,P(n) 均成立。

解釋

在這個證明中,歸納推理的過程如下:

  1. 首先證明 P(0) 成立,即公式在 n = 0 時成立。
  2. 然後證明從 P(m) 成立可以推導出 P(m+1) 也成立。(這裡實際應用的是演繹推理法)
  3. 根據上兩條從 P(0) 成立可以推導出 P(0+1),也就是 P(1) 成立。
  4. 繼續推導,可以知道 P(2)、P(3) 也成立。
  5. 從 P(3) 成立可以推導出 P(4) 也成立。
  6. 等等等等,不斷重複。(這就是所謂「歸納」推理的地方)
  7. 我們便可以下結論:對於任意自然數 n,P(n) 成立。

數學歸納法的變體

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

從 0 以外的數字開始

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

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

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

相關條目

歸納推理法

演繹推理法

結構歸納法

返回到 "Dz902/沙盒/数学归纳法" 的使用者頁面。