張貼日期：Mar 20, 2017 2:22:25 PM
作者：陳宏賓 副教授（國立中興大學應用數學系）
英國哲學家培根提出「歸納法」是以系統的觀察與實驗建立通則，並由觀察到的事實推演出普遍結論或定律。目前人類累積的自然及人文科學知識或理論主要源自於觀察（Observation）、實驗（Experiment）、歸納（Induction）這三個核心步驟。在教育場域裡，數學被詬病的問題很多，而其中一個就是「缺少觀察、實驗、歸納這樣三個理所當然應該要有的知識建立過程」。會有這樣的認知我認為很可能是因為數學少了像物理、化學、生物等自然科學的實驗課程，很多人就以為數學理論的建立沒有經過這些步驟。這是誤會，而且誤會大了。
先來看看下面這張表格，其中第 n 個三角數(triangular number)的定義是等於 1+2+…+n 的數；而第 n 個平方數(square number)就是大家熟知的 n2。
你觀察到甚麼有趣的規律了嗎？
這裡列舉幾個供大家參考：
A. 每一個正整數加上前一個正整數(比它小那個)會等於跟它同一列的那個奇數，例如 3+2=5, 4+3=7…。
B. 每一個三角數加上前一個三角數等於跟它同一列的平方數，例如 1+3=4, 3+6=9,…。
C. 每一個平方數減去前一個平方數等於跟它同一列的奇數，例如 36-25=11, 25-16=9,…。
藉由觀察以及有限次數的實驗，我們可以得到諸如 A、B、C 的結論。不過，要成為數學定理可得經過嚴格的證明才行，這裡派上用場的數學證明技巧就是所謂的－「數學歸納法」。
數學歸納法（Mathematical Induction）
今天要談的主角數學歸納法（Mathematical Induction）是數學史上超級無敵有用的工具之一，如果收集所有的論文來算引用次數的話，數學歸納法絕對是名列前茅。數學歸納法概念的起源眾說紛紜，集合論大師康托爾（Georg Ferdinand Ludwig Philipp Cantor 1845-1918）曾在其書中指出巴斯卡（Blaise Pascal 1623-1662）為創始人，這個巴斯卡就是巴斯卡三角形那個巴斯卡，後來經朋友提醒才改口 Franciscus Maurolycus 在 1575 年發表的算術著作才是真正的起源，上述的 A、B、C 就是他在著作裡提到的其中三個發現，從動手一一寫下數字填入表格，藉由敏銳的觀察力找出可能的規律，然後進行有限次數的實驗，最後利用歸納法的概念得到結論。我們可以大膽這麼說吧，「數學的實驗在 500 年前就有了呢」。除此之外，還有一些人認為早在西元前三百年，歐幾里得在「質數有無窮多個」的證明中就隱含了數學歸納法的概念。隱含表示沒有明確的講清楚，也因為這樣才使為了追朔根本的後人沒有統一的看法，這麼好用的東西是後來19世紀英國邏輯學家狄摩根（Augustus De Morgan 1806-1871）才將它嚴謹地形式化。你想的沒錯，這個狄摩根也就是當初發現狄摩根定律的那個狄摩根。
介紹數學歸納法之前，我們先回頭來看看著名的皮亞諾第五公設：
阿鬼，你還是說中文吧。
假設Ｓ是自然數的子集合，如果１是Ｓ中的元素，且Ｓ中的每一個元素加１後還是Ｓ中的元素，則Ｓ就是所有的自然數。這樣是有比較好懂逆？？
數學歸納法就是以此為基礎，當要證明某一數學敘述 P(n) 對於所有自然數都成立時，我們會證明：
1. P(1) 成立
2. P(n) 成立則保證 P(n+1) 也成立
亂用數學歸納法的飯桶
很難想像這麼簡單的原理，居然威力無窮得不得了！不過，好用歸好用，使用上還是有一些限制的。打個比方，我們下面不妨試著想像自己是個飯桶（喂～你自己才是飯桶ＸＤ），要用數學歸納法來證明 飯永遠吃不飽：
證明
一粒飯很明顯吃不飽，正確！
假設ｎ粒飯也吃不飽。
因為ｎ粒飯吃不飽，所以再多吃１粒飯也不會飽，故吃ｎ＋１粒飯也吃不飽。根據數學歸納法，飯永遠吃不飽，得證。得證你個頭啦！
這個結論很明顯是不對的，原因在於飯能不能吃飽這句話無法使用數學精確地描述出來，所以對於 P(n) 的敘述我們要求必須要能夠以數學符號表示清楚才行。
數學歸納法的正統起手式
為了讓大家瞭解一下正確使用方法，我們來證明前面提到的 A：每一個正整數加上前一個正整數(比它小那個)會等於跟它同一列的那個奇數。換成數學語言可以寫成，n + (n-1) = On ，這裡 On 指的是第 n 個奇數。
證明
很明顯 2+1 = 3 = O2。
假設 n + (n-1) = On 成立。則 (n+1) + n = On +2 = On+1 (最後這個等式成立是在已知第 n 個奇數加 2 等於第 n+1 個奇數的前提下)。由數學歸納法得知，A 是對的。
有興趣的讀者可以自己練習一下證明 B 跟 C，如果覺得太簡單的朋友，可以試著證明這個習題：
對於任意自然數ｎ，可以將｛1, 2, 3, …, 2n｝兩兩分組，使得每一組兩數字的和都是質數。
你可能心想「啊！該怎麼開始呢…..，就先從實驗開始吧。」
｛1, 2｝的和是 3，正確。
｛1, 2, 3, 4｝可以分成｛1, 2｝｛3, 4｝分別的和是 3 跟 7 都是質數，正確。
｛1, 2, 3, 4, 5, 6｝可以分成｛1, 2｝｛3, 4｝｛5, 6｝分別是 3 跟 7 跟 11 都是質數，正確。
｛1, 2, 3, 4, 5, 6, 7, 8｝照這樣分成｛1, 2｝｛3, 4｝｛5, 6｝｛7, 8｝分別的和為 3、7、11、15 都是質…
呃，等等！15 不是質數！！！
「…這道題目真的是正確的嗎？」
「會不會有其他種分法呢？」
．
．
．
「啊！想到了，可以分成｛1, 2｝｛3, 4｝｛6, 7｝｛5, 8｝分別的和為 3、7、13、13 都是質數！」
一直這樣做實驗下去…
到了｛1, 2, …, 20｝都還是對的！
終於！
也到了該相信它是正確的時刻了，剩下的證明就交給你囉～
誰說數學沒有實驗課呢？
參考文獻
1. W. H. Bussey, The Origin of Mathematical Induction, The American Mathematical Monthly, Vol. 24, No. 5 (May, 1917), pp. 199-207.
2. Mathematical induction, Mathwikia, http://math.wikia.com/wiki/Mathematical_induction
3. 數學歸納法，數學傳播第十卷第四期，董世平。
4. Alexander Bogomolny, Mathematical Induction from Interactive Mathematics Miscellany and Puzzles
http://www.cut-the-knot.org/induction.shtml, Accessed 20 March 2017