數學歸納不是經驗歸納

昨夜躺在床上輾轉反側，恍惚間，想起了中學時代的事。當時數學書上有一句話：」由數學歸納法，..."而在書上又沒有明確的證明過程，於是有同學問老師，數學歸納是什麼？老師當時怕我們不明白，就說：「你們先證明1是對的，然後證明2是對的，再證明3也是對的，於是歸納出n都是對的。」於是這種「經驗歸納」的錯誤理解就植入了我的腦中。

前幾天又在某個回答的評論區里看見了」數學歸納「這四個大字，我突然明白，把數學歸納和「經驗主義」劃等號的觀念，不在少數，很多人一提到數學歸納，就覺得是根據經驗。

我盡我的力寫下這篇科普文，希望至少能幫助打破這種錯誤的理解方式。

在介紹數學歸納前，先想像一下爬梯子。我們爬上第一級，只會考慮怎樣去爬上第二級，我們不會一下子想到怎樣爬第三級、第四級甚至最後幾級。數學歸納法與此很相似。首先，需要證明的東西必須像梯子一樣，滿足well-ordering principle（良序）。我們每爬上一級梯子都知道下一級在哪。舉個例子，正整數是否良序的呢？是的。我們證明了3滿足某個命題，下一個必然是取4。而有些集，雖然是良序的，但這個良序很難被構造出來。（向評論區學習了，感謝）

接下來就來正式介紹一下數學歸納。介紹完之後，希望能稍微糾正「經驗歸納」那種錯誤的理解。

總體而言，數學歸納分為兩個步驟：（我們要證明的命題是P(n)，意思是所有取值範圍內的n均滿足命題P）

第一步 Base Case：取滿足取值範圍的最小的數，證明這一個數滿足命題

第二步 Inductive Step：假設命題P(n)成立，推證命題P(n+1)成立。

這裡有人會站起來拍桌子了：「數學老師說，假設結論正確，去證明結論的做法是數學中的大忌啊！」

別急，咱們來分析一下這個步驟。我們確實在Inductive Step中假設了結論正確，但是我們證明的不是結論P(n)，我們證明的是P(n+1)，也就是前文提到的「下一步」。也就是說，我們只把目光放在下一步，只要這一步正確，下一步也正確。但是這樣還不夠，萬一這一步錯了呢？那下一步的正確性就證明不了了。所以我們在一開始就做了Base Case。我們證明了第一步是正確的，那麼根據Inductive Step，第二步也是正確的。既然第二步也是正確的，那麼第三步也是正確的。以此類推。這個過程很像多米諾骨牌，Base Case就是一開始那一推，沒人推的話，擺的再好也不會倒。而Inductive Step就是骨牌的擺放，每一個骨牌的擺放都不能決定整一套多米諾骨牌的倒下，但是可以決定下一個骨牌肯定能倒下。

幾乎每一套教材都會用等差數列求和通項公式的證明來當作例子，可能是因為簡單好理解。那麼既然是科普向的文章，我也用這個簡單一些的例子來作說明了。

（為了方便科普，我也不用 表示了）

公式的右半部分什麼意思呢？小學背過的口訣：首項加末項乘以項數除以二。

開始證明：

1. Base Case：證明P(1)滿足此公式

左邊＝1= ＝右邊 成立

2. Inductive Step

假設 成立，證明 成立（所謂P(n+1)，就是把所有n的地方全部替換成n+1）

證畢。

最後，我知道很多人還是會覺得「數學歸納不能證明東西「。我理解，我第一次接觸數學歸納的時候，心裡也是"WTF is this shit?"

這次我們不用多米諾骨牌解釋，我們來認真地談一談數學歸納的合理性。（科普部分至此完，以下證明需要有一定的數學基礎（集合相關知識）才能比較好理解）

反證法證明數學歸納合理性：假設存在一個取值範圍內的數 j 不滿足P(j)。

1. 定義 ( )。
2. 如果F非空，則F存在最小元素z使得命題P(z)為假。
3. P(1)，即1滿足P，所以 。
4. z是F中最小的元素，也就是說P(z-1)為真。
5. 但是 ，即 ，所以
6. 為真，此處與F的假設矛盾。

故 對所有 成立。

此處再回顧一下數學歸納的前提：well-ordering principle（良序）。

至此，粗略地介紹了一下數學歸納法。希望能夠打破那種「數學歸納＝經驗主義」的錯誤認知。數學歸納是一種證明的方法，既然是證明，就需要嚴謹的邏輯。