淺談數學歸納法

數學歸納法是數學中非常有力的一種證明方法。能用數學歸納法證明的往往是與自然數n有關的命題P(n)。通常的結論是命題P(n)對所有大於或等於某個自 然數m成立，m一般都是較小的自然數，比如1或者2。證明步驟大致分為兩步。第一，驗證命題P(m)成立，也就是基礎部分成立。然後再證明歸納假設部分： 如果命題P(k)為對，證明命題P(k+1)也對。如兩部分都得到證明，數學歸納法原理告訴我們，命題P(n)對所有大於或等於m的n成立。

先看一個簡單的例子。用3^n表示3的n次方。

現有3^n個外表一模一樣的球，已知其中一個壞球較輕(或較重)，剩下的輕重一致，能否僅使用n次天平便找出壞球？

答案是能，但如何證明呢？

用P(n)表示如下命題：現有3^n個外表一模一樣的球，已知其中一個壞球較輕(或較重)，剩下的輕重一致，如果n大於或等於1，僅需使用n次天平便能找出壞球。

換句話說，我們需要證明P(n)對n大於或等於1為真。

如何證？分兩步證。

第一步，n=1時命題對不對？在n=1時，P(1)就是在已知壞球為輕或重的情況下，用一次天平就將3個球中的壞球找出。這個不難，假設壞球為輕，只需天平左右各放一球，剩下的放在地上。如左右平衡，則壞球在地上，否則輕的便是壞球。所以P(1)為真。

第 二步，假設P(k)為對，需要證明命題P(k+1)也對。這步也不難。將3^(k+1)個球分成三等份，每份都有3^k個球。天平左右各放一份，剩下的一 份放在地上。如左右平衡，則壞球在地上的那一份中，否則壞球便在輕的那一份中。換句話說，使用一次天平后，便能知道壞球在三等份中的哪一份中。

注意，在已知壞球為輕的情況下，由歸納法假設，P(k)為對，就是只需使用k次天平便能找出3^k個球中的壞球。

現在三等份之一中只有3^k個球，所以由歸納法假設，只需使用k次天平便能找出3^k個球中的壞球。加上第一次，(k+1)就能找出3^(k+1)個球中的壞球了。

於是我們證明了第二步也對，所以由數學歸納法原理命題P(n)對n大於或等於1為真。

接下來，我們用歸納法證明一個更為困難的命題。

我們要證明下面的結論Q(n)：假設n>1,現有(3^n-3)/2個外表一模一樣的球，其中一個是壞球，但不知是輕還是重，剩下的輕重一致，我們能夠僅用n次天平就找出壞球並告知輕重，並且第一次總是三等分總球數為三份且任取兩份分別放在天平的左右兩邊。

先看看Q(3)是什麼意思：現有12個外表一模一樣的球，其中一個是壞球，但不知是輕還是重，剩下的輕重一致，我們能夠僅用3次天平就找出壞球並告知輕重。

這個問題我們已碰過多次，頗為複雜難解。我們要用數學歸納法證明更一般的結論。

第一步，先證明Q(2)為對。也就是證明：3個外表一模一樣的球，其中一個是壞球，但不知是輕還是重，剩下的輕重一致，我們能夠僅用2次天平就找出壞球並告知輕重。

這個不難證。讀者朋友自己完成好嗎？

我們證明第二步，歸納假設部分：如果命題Q(k)為對，則命題Q(k+1)也對。也就是要證明，用(k+1)次天平，便可找出{3^(k+1)-3}/2個球中的壞球和輕重。

將{3^(k+1)-3}/2個球三等分，比如為L,R,B三份，每份有{3^k-1}/2個球。第一次稱球，天平左右各一份，左邊為L,右邊為R,B放地上。接下來如何稱第二次？

將L,R,B各分為兩組：分別是L_1和L_2,R_1和R_2,以及B_1和B_2。L_2,R_2和B_2各有3^（k-1）個球。於是L_1,R_1和B_1分別有{3^(k-1)-1}/2個球，合起來共有(3^k-3)/2個球。

我 們將L_1和B_2放在天平左邊，R_1和L_2放在天平右邊，B_1和R_2放在地上。這樣稱的目的如下。第一次稱，有三種結果：左重，右重或左右平 衡，第二次稱也有三種結果。如兩次稱球結果相同，則表示壞球沒有挪窩，必在L_1,R_1和B_1中。如兩次稱球結果不同，則壞球必在L_2,R_2和 B_2三組之一中。

具體討論兩次稱球結果不同如下。

如第一次結果為左右平衡，壞球在B中。如第二次結果為左重，則壞球必在B_2中且為重；如第二次結果為右重，則壞球必在B_2中且為輕。

如第一次結果為左重，壞球便在L和R中。如第二次結果為右重，則壞球必在L_2中且為重；如第二次結果為左右平衡，則壞球必在R_2中且為輕。

如第一次結果為右重，壞球便在L和R中。如第二次結果為左重，則壞球必在L_2中且為輕；如第二次結果為左右平衡，則壞球必在R_2中且為重。

換 句話說，經過兩次稱球，我們可以推斷，壞球要麼在L_1,R_1和B_1中，要麼在L_2,R_2和B_2三組之一中且輕重已知。如果是後者，用已經證明 過的P(k-1)，再用(k-1)次天平，就可把壞球找到。所以總共用了2+(k-1)=k+1次天平就可找到壞球並知輕重。

如果是前者，也就是壞球在L_1,R_1和B_1中，怎麼辦？

好辦。

這時，L_2,R_2和B_2中的球均為好球。所以第二次稱球，相當於將L_1和R_1分別放在左右兩邊，B_1放在地上。如前所述，L_1,R_1和B_1分別有{3^(k-1)-1}/2個球，合起來共有(3^k-3)/2個球。

好了，用歸納法假設的時刻到了。我們的歸納法假設是命題Q(k)為對，也即使用k次天平，就可將(3^k-3)/2個球中的壞球找到並告知輕重。這k次稱球，還包括了前述的第二次稱球。加上第一次，總共也用了k+1天平。

大功告成！我們證明了，如果命題Q(k)為對，則命題Q(k+1)也對。所以由數學歸納法原理，只要n>1，Q(n)總是為真。也就是：只要n>1，總可使用n次天平，就可找出(3^n-3)/2個球中的壞球並分出輕重。

呵呵，n=3時，那個曾叫我們頭疼的12個球問題，不過是一個小小特例。當n=4時，僅使用4次天平，就可找出39個球中的一個壞球並告知輕重。用5次天平，就可找出120個球中的一個壞球。等等，等等，以此類推。