逆向思维的力量——从均值不等式谈起

经常有人会问，怎样衡量一个人的算法能力呢？数据结构？抽象思维？奇思妙想？答案多种多样，莫衷一是。不过如果我说出一项，相信没人会反对，那就是数学能力。一个数学高手未必是算法能人，这是由他研究数学的分支所决定的；不过一位算法强者必定是数学天才，这是由算法与数学的紧密联系所决定的。

暑假里为了给自己充电，阅读了《具体数学》的前几章，忽然感觉自己之前引以为傲的所谓的“数学天赋”真的不值一提，原来数学可以在大家的笔下散发出如此美丽的气质。《具体数学》的作者之一Knuth相信喜欢研究算法的同学一定不陌生，他就是计算机领域的神级读物《计算机程序设计艺术》的作者，图灵奖得主；而本书据说也是根据神书的第一章扩充而来。下面仅以一个例子来说说《具体数学》讲的数学到底有多具体。

这个定理对于任何一个高二年级以上的同学来说都是非常熟悉的，而且我们通常亲切地称之为均值不等式，对于n=2的情形还是高中考试中的重要考点。不过，对于这种基本形式，如何证明呢？

事实上，均值不等式的证明方法就如同勾股定理的证明方法一样多得不得了，不过我们最容易想到的就是数学归纳法：

由P(k)到P(k+1)的过程并不容易，我们吃尽了苦头才最终证明了这个定理：

也许有人会问，这个证明和《具体数学》有什么关系呢？实际上，接下来我要说的证明方法来自这本书第一章后面的练习题。

练习题给出的引导证明方法也是基于数学归纳法，但这种数学归纳法的思路是完全相反的，绝对给人耳目一新的感觉。

反向数学归纳法：

设P(n)表示一个与自然数n有关的命题，若

（1）P(n)对无数多个自然数n都成立；

（2）假设P(k+1)成立，可推出P(k)也成立；

则P(n)对一切自然数n都成立。

上述反向数学归纳法的正确性可以用反证法得到：假设命题P(n)满足那两个条件，但对于自然数m不成立，即P(m)不成立，那么显然P(m+1)也不成立，这可以看作是第（2）个条件的逆否命题。同理P(m+2)，P(m+3)…均不成立，换句话说P(n)对于n≥m均不成立，也就是P(n)仅对n的自然数成立，然而这与条件（1）矛盾，因此假设错误，反向数学归纳法是合理的。

用反向数学归纳法证明均值不等式的优势在于避免了正向的从P(k)到P(k+1)的繁琐推导：

显然，我们能够得到P(2k)。因此，我们可以通过2个P(2)得到P(4)，继而得到P(8)，P(16)…P(2^j)，只要j->+∞，我们就可以得到P(n)对无数多个自然数n都成立的结论，因此反向数学归纳法的两个条件都得以满足，因此我们成功证明了均值不等式。

两种思维，一正一反，我们不得不惊叹数学惊人的力量和迷人的气质。对于这个问题，我们如果走正向思维，中规中矩地用数学归纳法，需要精心细致地凑，并需要一个引理做铺垫才能顺利地得到结果；而如果我们反其道而行，使用反向数学归纳法，看似有些笨拙，但实际执行却相当容易：从大规模的数据向小规模的数据证明只需要将多余的数据实例化就行了（如上述证明中的P(k+1)到P(k)只需令a(k+1)为前k个数的算术平均值）。而无数的条件看似困难，其实只要我们打破常规思维，重新从正向进行推导，并由小规模数据的结论基于某种模式（如上述证明中的由P(2)和P(k)得到P(2k)）得到大规模数据的结论，那么无数的问题就迎刃而解了。

在解决均值不等式这个问题上，我们充分见识了怎样将逆向思维用于数学中。举的例子只是《具体数学》的冰山一角，更多的丰富营养等待着读者自己去汲取。不过，解决问题的理念是类似的：打破常规，反其道而行，有时真的会柳暗花明又一村。