趣味数学 （十一）浅谈数学归纳法

数学归纳法是数学中非常有力的一种证明方法。能用数学归纳法证明的往往是与自然数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个球中的一个坏球。等等，等等，以此类推。