歸納還是演繹
首先我們要搞清楚，數學歸納法，不是哲學上所講的歸納推理（ inductive reasoning） ，反而比較接近哲學領域所講的演繹 （deduction）推理。所謂的歸納推理，是基於對特定目標觀察的結果，把「性質」或「關係」類推至類型，或者是基於對反覆現象的觀察，所推理出來的規律或公式。歸納推理的結論只是有較大的機率為真，但不代表一定為真。
而演繹推理則是從已知事實為前提，必然得出的結論，如果前提為真，則結論必然為真。數學歸納法是基於一組已知的前提，推演出一個必然為真的結論，所以這個證明方法的精神是 deductive reasosing ，不是 inductive reasoning。
數學歸納法的基本敘述
Udi Manber 在他的書裡第二章末，參考文獻與進階讀物一節裡提到，數學歸納法是由 Francesco Maurolico 所發展出來的，事實上，數學歸納法的基礎可以上溯至更早的希臘時代的歐幾里德
（Euclid），維基百科可以找到數學歸納法的歷史介紹，簡明扼要但資料豐富，有意者可自行深入研究。
最常見的數學歸納法敘述，是說一個關於自然數的命題 P，當這個命題符合以下兩個條件時，則這個命題對自然數恆真：
- P(0) 成立 (有的情況是講P（1）)
- 當 P(n) 成立，則 P(n+1) 也成立
或者我們用英文的敘述（對於看不慣中文翻譯的人來說，用符號和英文反而更親切，不是嗎？）：
- The basis: P(0) is true.
- The inductive step: If p(n) holds, then P( n + 1) holds too.
換句話說，當上面兩個條件成立，P(n) is true for all natual numbers 。
用矛盾法（contradiction）證明數學歸納法的正確性
從高中到大學，我們學習數學歸納法，都是被動的背誦數學歸納法的證明手法，鮮少在課堂上探討歸數學納法可以證明命題敘述對在自然數這個集合裡一定是正確的。其實我們可以用矛盾（又稱歸謬證明法 - Proof by contradiction）法來驗證證明這個方法的正確性。
我們的前提如下：
- P(0)
- For all n ≥ 0, P(n) ⇒ P(n + 1)
然後我們現在要證明對所有大於零的自然數，P 這個命題恆真，就是
For all m ≥ 0, P(m) is true ...................................... （3）
接下來就是證明的核心，假設 （3）是錯誤的，那我們一定可以找到一個最小的數 m' 使得 P(m') 不成立，我們現在要證明這個假設是有衝突的，所以 （3） 不可能是錯的，（3）必須是真的。
首先， m' 不可能是 0，因為前提 （1） 已經告訴我們 P(0)必須成立，所以這個 m' 如果存在，一定大於 0。當我們找到這個所謂的 m' ，我們知道前提 P（m' - 1） 是成立的，因為 m' 是最小的令命題 P 不成立的數字，但是前提（2）告訴我們，P(m'-1+1)=P(m) 這個敘述必必須為真。這和我們的假設是衝突的，所以不可能找到令 （3）不成立的數字m'。換言之，P（x）這個敘述對於所有自然數都成立，我們已經證明數學歸納法在前提確立的狀況下，是打不破的。
皮阿諾公設(Peano's Axioms)
用今日數學的術語來說，數學歸納法就是皮阿諾公設(Peano's Axioms)中的第五公設。所謂公設（或稱公理 axiom），就是在某些學門中不需要證明，但卻必須被承認的敘述或命題，有的書籍翻譯為公理。公理是一門學問的基礎，這門學科的所有理論、定理，必然可以由這些最基礎的公理推演而來，如果基礎不被承認，這門學科也就無從存在，公設的重要性由此可見。
義大利數學家 Giuseppe Peano (皮阿諾) 在 1889 年以拉丁文寫作一本小冊子 Arithmetices principia, nova methodo exposita ( The principles of arithmetic, presented by a new method )，這本書將自然數的性質抽象化得到一組公設。希望藉著這組公設，透過邏輯的推演，可以演繹出自然數的所有性質。 皮阿諾把每一個自然數的下一個稱為這數的「後繼者」(successor)，用後繼者的說法， 這組皮阿諾公設可以寫成下面的形式（括弧裡是用符號的寫法，其中 n+ 表示自然數 n 的後繼者）:
- 0是一個自然數。
- 若x是一個自然數，則另有一個自然數X'(緊隨X之後)。X'稱為X的直接繼數。
- 0不是任何數的後繼者
- 對任何自然數X與y，若X'=Y'，則X=Y。
- [歸納原理]若P是一個性質(Property)，並且(i)0其有性質P；(ii)若任何自然數X具有性質P：則X'具有性質P，則所有自然數其有性質P。
數學歸納法不同的面貌
標準的數學歸納法證明，可以分為三個部分
- The Base Case (in the domino analogy, this shows the first domino will fall)
- The Induction Hypothesis (in the domino analogy, we assume that a particular domino will fall)
- The Inductive Step (in the domino analogy, we prove that the domino we assume will fall will cause the next domino to fall)
只要遵循以上三部曲的建構方式，通常都能順利找到證明的思路，發展出 induction step 來證明所欲證明的標的。事實上，在作數學歸納法證明時，有許多技巧上的變化，比如說：
☆（１）先證明ｎ＝１，ｎ＝２時命題成立；
（２）假設ｎ＝ｋ－１，ｎ＝ｋ－２的時候命題成立
（３）證明在此情形下，ｎ＝ｋ時命題也成立。
或者像這樣
☆（１）先證明ｎ＝１到ｍ時命題成立；
（２）假設ｎ＝ｋ的時候命題成立
（３）證明在此情形下，ｎ＝ｋ＋ｍ時命題也成立。
數學歸納法，並不是只有一個面貌，經過長久的發展，數學歸納法已經發展出許多的變異模式，適用於不同的場合與目的，甚至有些數學家開發出將數學歸納法延伸至自然數以外領域的模型出來。以最精簡的符號來表達，我們一般常見的數學歸納法的變化形式可能包括以下幾種情形：
Standard Formulation
- The basis: P(0) is true.
- Induction hypothesis: assume P(n=m) holds.
- The inductive step: If p(m) holds, show that P( m + 1) holds too.
Strong Induction
- The basis: P(0) is true.
- Induction hypothesis: assume for all n <= m, P(n) holds.
- The inductive step: If p(n) holds, show that P( n + 1) holds too.
Reverse Induction
- P(M) is true for some M
- If P(n=k+1) holds, show that the property holds for n = k.
依照上述證明方式，我們得到結論： The property holds for all values n <= M
Transfinite Induction
Transfinite induction 一般而言是應用在 well-ordered set 上，通常只有真正念數學的人，才會關心這個咚咚吧？ 根據 PlanetMath 的說明， Transfinite induction 的定義如下：
證明的陷阱，切記！切記！
前輩數學家華羅庚曾經講過一個故事 ：一位買主買了一隻公雞回家。第一天，餵公雞一把米；第二天，又餵公雞一把米；第三天，還是餵公雞一把米。連續十天，每天都餵給公雞一把米。公雞就這十天的經驗，下了一個結論說：每天一定有一把米可吃。但是就在得出這個結論後不久，家裏來了一位客人，公雞就被宰殺成為盤中飧請客人了(這個故事可以在昌爸工作坊找到)。
有人建議把數學歸納法想像成骨牌效應（falling dominos ），一張骨牌倒下來，下一張骨牌接著倒下去，就這麼一張一張倒下去，用遠不會停。問題就在這邊，我們必須確認一張骨牌一定接著一張，才能確保數學歸納法的正確與適用。
換句話說， P(n) 成立，不代表 P(n+1) 一定成立，千萬不要認為理所當然，我們的任務是確認 P(n) ⇒ P(n + 1)，不是默認 P(n) ⇒ P(n + 1)。
為什麼寫
原本只是打算在複習演算法時，順手記錄看書時的想法，但是在唸書時，看到第二章，在回顧自己學習數學歸納法的過程時，冒出許多想法，所以就順手把找到的東西發展出一篇完整的東西。
謝謝...
ReplyDelete你這篇關於 Principle of M.I. 的整理, 獲益良多.