※ 引述《roger00 (Stage Column(?))》之銘言：
: 助教你好,最近做證明題有一些問題,不知道能否為我解答?謝謝!
: (i) 為什麼數學歸納法是正確的?
: (ii) 數學歸納法使用上有兩種:
: Type A 當 n= c1,c2 時,敘述成立 (先試幾個實例)
: 假設 n= k 時,敘述成立
: 推到 n= k+1 敘述亦成立,則 對於所有c1,c2以上的正整數 敘述都成立
: Type B 當 n= c1,c2 時,敘述成立 (先試幾個實例)
: 假設 n<= k-1 時,敘述成立
: 推到 n= k 敘述亦成立,則 對於所有c1,c2以上的實數 敘述都成立
: 這兩種分別是離散型和連續型的數學歸納法,兩種證明方式都是正確的嗎?
(i)
可以把數學歸納法看成是邏輯推論的結果.
如你所言,數學歸納法有2個主要的部份
我們若想証明 P(n) is true for all integers n with n>=n0 這件事,
可以利用証明以下2件事達成
(1) the base step: P(n0) is true.
(2) the induction step:
"P(n) is true" => "P(n+1) is true", for all integers n with n>=n0
那麼藉由不斷地套用(2), 我們可以知道
"P(n0) true" => "P(n0+1) true" => .......
但是這只是一種型式, 你也可以藉由証明
(1) "P(n0) is true" and "P(n0+1) is true"
(2) "P(n) is true" => "P(n+2)" is true", for all n>=n0
來得到一樣的結論
總歸一句, 將它視為邏輯上的結論
若你問的是更根本的理由, 數學歸納法在正整數上會成立,
是因為正整數滿足well-ordering principle
(任何非空的正整數集合, 都可以找到當中一個最小的元素)
換句話說, 任何其它具有這種特性的結構, 你都可以在它上面套用數學歸納法
(例如負整數, 每個負整數集合你都可以找到一個當中最大的元素)
(ii)
這裡的Type B不太正確唷, 理由是我們沒辦法由Type B裡的base step及induction step
得到你所提的結論