以下文字節錄及修改自 離散數學(第二版)(修訂版) Liu Chung Laung 著 / 黃淳權 譯 第19, 20, 22, 23頁。
數學歸納法(Principle of Mathematical induction)
對一個給定包含自然數n的命題，若能證明：
1.當n=n0時，命題成立。而且，
2.假設n=k(k>=n0)時命題成立，則n=k+1時命題亦成立。
則我們便可得結論：對所有自然數n>=n0，命題恆成立。
例：
有一個國王想知道到底數學家們有多聰明，於是把全國最好的數學家們都召至皇宮中。國王告訴他們：「我已經將一些白帽子戴在你們某些人的頭上，其他的人則已戴上了黑帽子，你們不許交談，只准彼此觀察，我現在離開，每隔一小時我會回來一次，當我回來的時候，我希望那些知道自己戴白帽子的人能告訴我。」結果是，若有n個人原先被戴上白帽子的話，他們便會在第n小時告訴國王說他們知道自己戴的是白帽子。這到底是為什麼?
我們用數學歸納法證明如下：
1.當n=1時，也就是說只有一位數學家被戴上了白帽子，既然國王已經說過某些數學家會被戴上白帽子(國王不會說謊)，那麼當這位唯一被戴上白帽子的數學家發現其他所有的數學家都戴著黑帽子的時候，他就會馬上知道只有他是戴白帽子的，於是他便會在第1個小時告訴國王(國王第一次回來的時候)說他戴的是白帽子。
2.為了幫助了解，在此解釋只有兩個數學家被戴上白帽子的情況，其中一名被戴上白帽子的數學家發現只有一名數學家戴的是白帽子，但是他卻未在第一個小時告訴國王，可見不只有一人戴的是白帽子，於是這兩名聰明的數學家都知道自己也戴了白帽子，並且在第二小時告訴國王。
3.假設共有k個數學家被戴上白帽子，並且他們會在第k個小時發覺自己戴的是白帽子而告訴國王。如果有k+1個數學家被戴上白帽子，那麼每個戴白帽子的數學家便會發現共有k個數學家戴的是白帽子，但是在第k小時，卻沒人告訴國王說他戴的是白帽子，可見有多於k個人戴的是白帽子，於是每個戴白帽子的數學家都會知道自己戴的也是白帽子，並在第k+1個小時告訴國王。
強數學歸納法(The Principle of Strong Mathematical induction)
對一含有自然數n之命題，若我們能證明：
1.n=n0時，命題成立。
2.假設n0<=n<=K命題成立時，n=k+1命題亦成立。
則在n>=n0時，此命題皆可成立。
例：
我們欲證明大於或等於2的正整數為質數或質數的乘積
1.當n=2時，2為質數，故命題成立。
2.假設2<=n<=k時，命題成立。考慮整數k+1的情況，若k+1為質數，命題成立。或k+1非質數，則k+1可分解為p,q，其中p<=k，且q<=k。根據假設，p及q必為質數或質數之乘積，故k+1亦為質數的乘積。綜上所述，k+1為質數或質數之乘積。
請先 登入 以發表留言。