「數學歸納法」其實不歸納

「數學歸納法」其實不歸納（Mathematical Induction is not induction at all）
中央研究院數學所李國偉研究員/中央研究院數學所李國偉研究員責任編輯

通常教科書裡講解數學歸納法時，會出現類似下面的陳述：給定一個關於正整數 $${n}$$ 的敘述 $${P(n)}$$，如果想證明 $${P(n)}$$ 對於所有正整數 $${n}$$ 都成立，只需做兩件事：

１、（歸納基礎）證明 $${n}=1$$ 時，$${P(1)}$$ 成立。
２、（歸納步驟）假設 $${n}={k}$$ 時 $${P(k)}$$成立，證明當 $${n=k+1}$$ 時，$${P(k+1)}$$ 成立。

當這兩件任務完成後，$${P(n)}$$ 就對所有正整數 $${n}$$ 成立了。

在證明涉及正整數的命題時，數學歸納法是非常有威力的工具。可是學生初次接觸這種論證的方式時，往往會產生一些困惑。學生看完這種陳述，聽完老師的講解，以及作完一些例題之後，可能仍感覺到把 $${n}$$ 寫成 $${k}$$ 好似變魔術。當 $${n}={k}$$ 時，$${P(k)}$$ 不就是 $${P(n)}$$ 了嗎？那你已經用了 $${P(n)}$$ 成立了，幹嘛還要再證明 $${P(n)}$$ 都成立呢？

解除這個困惑的關鍵在於理解「歸納步驟」是一個使用「真值蘊涵」的條件句，如果這一步作得正確，並不保證條件句的前提永遠為真。只保證當前提為真時，條件句的結論也為真。換句話說，即使 $${P(n)}\rightarrow{P(n+1)}$$ 對於所有 $${n}$$ 均為真，並不必然推導出 $${P(n)}$$ 對於所有 $${n}$$ 為真。

我們來看兩個有毛病的例子：

錯例１：試證 $$\displaystyle 1+2+3\mbox{…}+n=\frac{n(n+1)}{2}+1$$
錯證：

令 $${P(n)}$$ 表示敘述 $$\displaystyle 1+2+3\mbox{…}+n=\frac{n(n+1)}{2}+1$$。

假設 $${n}={k}$$ 時 $${P(k)}$$ 成立，即 $$\displaystyle 1+2+3\mbox{…}+k=\frac{k(k+1)}{2}+1$$。

當 $${n}={k+1}$$ 時，$$\displaystyle 1+2+3\mbox{…}+k+(k+1)=\frac{k(k+1)}{2}+1+(k+1)=\frac{(k+1)(k+2)}{2}+1$$

即 $${P(k+1)}$$ 成立，所以 $${P(n)}$$ 對於所有正數 $${n}$$ 都成立。（證畢）

這個例子通常是用來說明沒有驗證「歸納基礎」的錯誤，因為 $${P(1)}$$ 其實斷言一個荒謬的結論 $${1=\frac{1(1+1)}{2}+1=2}$$。而我們在此要強調的是，錯證雖然沒有正確使用數學歸納法，可是從 $${P(k)}$$ 到 $${P(k+1)}$$ 的推論本身並沒有錯誤。根據「真值蘊涵」的規定，條件句的前提與結論都為假時，條件句本身還是為真。

錯例２：試證「任何 $${n}$$ 個人都同高」。
錯證：

令 $${P(n)}$$ 表示敘述「任何 $${n}$$ 個人都同高」。

當 $${n=1}$$時，敘述變為「任何一個人都同高」，顯然成立。

假設 $${n=k}$$ 時敘述成立，即「任何 $${k}$$ 個人都同高」，那麼當 $${n=k+1}$$ 時，

將 $${k+1}$$ 個人記為 $$A_1,A_2,\mbox{…},A_k,A_{k+1}$$，由歸納法假設可知 $$A_1,A_2,\mbox{…},A_k$$ 都同高，

而 $$A_2,\mbox{…},A_k,A_{k+1}$$ 也都同高，所以 $$A_1,A_2,\mbox{…},A_k,A_{k+1}$$ 都同高。

經由以上的「歸納基礎」與「歸納步驟」兩階段，$${P(n)}$$對於所有正整數$${n}$$都成立。（驗畢）

這個例子形式上具有數學歸納法的兩項要件「歸納基礎」和「歸納步驟」，可是在「歸納步驟」時所作的推論是有問題的。要想使推論正確，必須 $${k}\ge 3$$。如此不管拿掉尾巴那個人，或是拿掉領頭那個人，都還有人剩下當作共同比較的依據。這個例子裡從 $${P(k)}$$ 到 $${P(k+1)}$$ 的推論本身就不為真，自然也無法保證 $${P(n)}$$ 對於所有正整數 $${n}$$ 都成立了。

有教科書對於「歸納法」的意義作出如下的說明：「歸納法是對一些個別的事物詳加觀察、紀錄，探討這些個別事物的共同特性，然候將所得到結果推廣到其他未經觀察的同類事物中，從中概括出同類事物一項普遍性結論。」

這是對於一般科學方法裡的「歸納法」的說明，其實「數學歸納法」並沒有執行任何歸納，它純粹是條件句的運用，是屬於演繹邏輯的範圍。以「數學歸納法」證明的命題，也許曾經運用「歸納法」幫忙找出恰當的敘述形式，但是證明的過程卻是演繹，演繹，再演繹。