数学中的自动化推演

17 世纪末，德国数学家莱布尼兹（Leibniz，1646～1716）在研究自然数 n 的组成方法。

同理他求出 P（5）＝7，P（6）＝11。这些恰恰是头几个质数。于是莱布尼兹觉得，他似乎得到了以下结论：P（n）是第 n－l 个质数。但当他检验数 7 的组成时，却得到 P（7）＝15，从而否定了自己脑海中曾经闪过的一个念头。据此，莱布尼兹对不完全的归纳作了如下深刻的评论：上述猜想“是骗人的归纳的极好例子”。

下面是一道相当精妙的归纳练习，它无疑能加深读者认识不完全归纳的局限性。

在一张纸上画一个圆周，可把纸面分割成两个部分；画两个圆周最多可把纸面分割成 4 个部分；画三个圆周最多可把纸面分割成 8 个部分。请问画n 个圆周最多可把纸面分割成几个部分？

也许有的读者脱口而出是 2n，那就大错而特错了！正确的答案应该是 n2

－n＋2。

那么，克服不完全归纳的局限，步向真理的阶梯该是什么呢？这就是我们即将讲述的一种科学方法——数学归纳法。下面的故事寓意极深，它提示了数学归纳法的真谛。

从前，一位画家为了测试他的三个徒弟对绘画奥妙掌握的程度，他把他们叫来，让他们用最经济的笔墨，画出最多马。

第一个徒弟在卷子上密密麻麻地画了一群马；第二个徒弟为了节省笔墨，只画出许多马头；第三个徒弟在纸上用笔勾出两座山峰，再从山谷中走出一只马，后面还有一只马只露出半截身子。

三张画稿交上去，评判结果是最后一幅画被认定为佳作。构思巧妙，笔墨经济，以少胜多！

这第三张画稿，只画一只半马，为何能胜于画一群马呢？原因在于：第

一张画虽然画了一群马，但却是有限的，第二张画虽对第一张画作了简化，但没有改变有限数的本质，第三张画则不同，在一只马后面带出的半只马，使人想象到隐没在山谷中行进着的一只又一只马，似乎无法尽数。

上面故事中的道理，被移植到数学上就是：要证明一个与自然数有关的命题是真命题，必须分两步：

验证当 n 取第一个自然数 n0 时命题成立；
假设 n＝k 时命题成立，证明 n＝k＋1 时命题也成立。

在完成上述两个步聚之后，便能断定命题对从 n0 开始的所有自然数 n 都成立。这，就是数学归纳法。

上述第一步是论证命题的基础，相当于前面故事中的第一只马；第二步

是判断命题的正确性，能否从特殊推广到一般的依据，相当于故事中的如下事实：即如果有一只马，背后必带有另一只马。这样，有了第一只，便有第二只马；有了第二只马，便有第三只马；⋯⋯如此等等，以至无穷！这个过程就是“自动化的推演过程”。

数学归纳法的两个步骤是必不可少的：没有第二步便成了不完全归纳，其局限性勿须多说。不过，第二步固然重要，第一步不能没有。没有第一步，第二步便成了空中楼阁，甚至会因此推出谬误。下面是 G·波利亚教授为说明这一问题而精心设计的一种“证明”。他试图“证明”一个有趣的论断： “任何 n 个女孩都有同样颜色的眼睛。”波利亚教授是这样写的：

对于 n＝1 这句话显然是对的，剩下的是从 n 推到 n＋1，为具体起见我将从 3 推到 4，而把一般的情形留给你。

让我把 4 个女孩子介绍给你，她们是 A、B、C、D。假设（n＝3）A、B、C 的眼睛具有同样的颜色；也假设（n＝3）B、C、D 的眼睛也具有同样的颜色。因此，A、B、C、D 四个女孩子的眼睛必定具有同样的颜色。

这就证明了 n＋1＝4 时的论断。又比如从 4 推到 5 的情形，当然也不会有什么困难。

波利亚果然“推出”了所有女孩子的眼睛颜色都是相同的。但这显然与事实违背；中国女孩是黑眼睛，美国女孩却多是蓝眼睛！那么毛病究竟出在哪里呢？波利亚教授解释道：问题出在第一步，从 n＝1 推到 n＝2 不成立，用此导致了谬误。

下面我们看一个用数学归纳法证明题的例子。

某次体育比赛，每两名选手都进行一场比赛，每一场比赛一定决出胜负，通过比赛确定优秀选手，选手 A 被确定为优秀选手的条件是对任何其他选手B，或者 A 胜 B，或者存在选手 C，C 胜 B，A 胜 C，如果按上述规则确定的优秀选手只有一名，求征：这名选手胜所有的其他选手。

证明：

（l）当 n＝2 时，命题显然成立；

（2）假设 n＝k 时，命题成立，即在 k 个选手的集合 x 中，A 胜其余 k

－1 个人。

今在集合 X 的基础上增加一个选手 B，组成集合β，则： 1°若 A 胜 B，命题显然成立；

2°若 A 负于 B，进一步分两种情况：

（Ⅰ）当 B 胜集合β中其他选手时，B 为唯一的优秀选手，命题成立；

（Ⅱ）假设当 B 对集合β中除 A 以外的选手有胜、负或全负时，不妨设B 负于 C，则因 A 胜 C，C 胜 B，B 胜 A，按规定 B 间接胜 C，这时，A、B 均为优秀选手，这与已知矛盾。

所以，当 n＝k＋1 时，命题成立，从而由（1）（2）得对任意自然数 n，命题成立。

数学归纳法是数学思维方法中最重要，最常用的方法之一，它的“自动化推演论证”过程十分完美地把特殊推广到一般，把有限推广到无限！