什麼是數學歸納法??

數學歸納法
維基百科，自由的百科全書
(重定向自數學歸納法)
跳转到： 导航, 搜索
數學歸納法是一種數學證明方法，通常被用於證明某個給定命題在整個（或者局部）自然數範圍內成立。除了自然數以外，廣義上的數學歸納法也可以用於證明一般良基結構，例如：集合論中的樹。這種廣義的數學歸納法應用於數學邏輯和電腦科學領域，稱作結構歸納法。
需要留意的是，數學歸納法雖然名字中有「歸納」，但是實際上數學歸納法並不屬於不嚴謹的歸納推理法，實際上是屬於完全嚴謹的演繹推理法。






目錄[隱藏]

1 定義
2 例子

2.1 證明

2.1.1 第一步
2.1.2 第二步
2.2 解釋
3 數學歸納法的變體

3.1 從 0 以外的數字開始
4 完整歸納法

4.1 超限歸納法
5 數學歸納法的證明或再形成
6 相關條目
7 外部連結



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


圖片參考：http://upload.wikimedia.org/wikipedia/commons/thumb/9/92/Dominoeffect.png/200px-Dominoeffect.png



圖片參考：http://zh.wikipedia.org/skins-1.5/common/images/magnify-clip.png
骨牌一個接一個倒下，就如同一個值到下一個值的過程。


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

證明第一張骨牌會倒。
證明只要任意一張骨牌倒了，那麼與其相臨的下一張骨牌也會倒。
那麼便可以下結論：所有的骨牌都會倒。

[編輯] 例子
假設我們要證明下面這個公式（命題）：

圖片參考：http://upload.wikimedia.org/math/5/6/4/5643bc131df5cdd3be011f4cfe17c613.png

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

[編輯] 證明

[編輯] 第一步
第一步證明的是這個公式在 n = 0 時是否成立。這裡要注意的是 0 = 0，而 0(0 + 1) / 2 = 0，所以這個公式在 n = 0 時成立。證明的第一步完成。

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

圖片參考：http://upload.wikimedia.org/math/9/4/6/946158b26392acfc1a736f128ae51580.png
（等式 1）
然後在等式等號兩邊分別加上 m + 1 得到

圖片參考：http://upload.wikimedia.org/math/4/8/b/48ba04091f49ba39b947999e497aa9e8.png
（等式 2）
這就是 n = m+1 時的等式。我們現在需要根據等式 1 證明等式 2 成立。通過因式分解合併，等式 2 的右手邊

圖片參考：http://upload.wikimedia.org/math/6/f/2/6f2c258d73ff64be33d87a5214981cbf.png

也就是說

圖片參考：http://upload.wikimedia.org/math/1/9/3/193c1b4b97eeccb51db9d03c5dfa3aef.png

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

[編輯] 解釋
在這個證明中，歸納推理的過程如下：

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

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

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

第一步，證明當 n = b 時命題成立。
第二步，證明如果 n = m (m ≥ b) 成立，那麼可以推導出 n = m+1 也成立。
用這個方法可以證明諸如「當 n ≥ 3 時，n2 > 2n」這一類命題。

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

證明當n = 0時式子成立.
證明當 m ≤ b 時成立,那麼當n = m + 1時式子也成立.
例如,這種方法被用來證明:

fib(n) = [Φn − (−1/Φ)n ] / 51/2
fib(n) 是第n個斐波納契數 和 Φ = (1 + 51/2) / 2 (即黃金分割). 如果我們可以假設式子已經在當 m and m − 1時成立,從 fib(m + 1) = fib(m) + fib(m − 1)之後可以直接了當地證明當m + 1 時式子成立.
這種方法也是第一種形式的特殊化:

定義 P(n) 是我們將證的式子,
接著用這個規則證明也就是等價於證明

式子用開始兩步證明當n屬於自然數時, '所有的m ≤ n 存在時 P(m) 成立 '

[編輯] 超限歸納法
最後兩步可以用這樣一步表示:

證明如果式子在所有的 n < m 成立,那麼式子在當n = m時也成立.
實際上這是數學歸納法的大多數通式,可以知道他不僅對錶達自然數的式子有效,而且對於任何在良基集(也就是一個偏序的集合,包括有限降鏈) 中元素的式子也有效(這裡 "<" 被定義為 a < b 若且唯若 a ≤ b 和 a ≠ b).
這種形式的歸納法當運用到序數(以 有序的和一些的良基類的形式)時被稱為超限歸納法. 他在集合論, 拓撲學和其他領域是一中重要的方法.
要區別用超限歸納法證明的命題的三種情況:

m 是一個極小元素,也就是沒有一個元素小於m
m 有一個直接的前輩,比m小的元素有一個大的元素
m 沒有任何前輩,也就是 m 是一個界限序數.
參見 數學歸納法的三種形式.

[編輯] 數學歸納法的證明或再形成
數學歸納法的原理作為自然數公理,通常是被規定了的(參見皮亞諾公理). 但是他可以用一些邏輯方法證明; 比如, 如果下面的公理:

自然數集是良序的。
被使用.
注意到有些其他的公理確實的是數學歸納法原理中的二者擇一的公式化. 更確切地說, 兩個都是等價的.參見數學歸納法的證明.

[編輯] 相關條目
歸納推理法
演繹推理法
結構歸納法

[編輯] 外部連結

Mathematical Induction, Examples[英文]


取自"http://zh.wikipedia.org/w/index.php?title=%E6%95%B0%E5%AD%A6%E5%BD%92%E7%BA%B3%E6%B3%95&variant=zh-hk"

... ok!!

咁我睇wiki咪得囉。