数学中的归纳与递推

2004-03-07欧阳维诚

初中生·博览 2004年3期

欧阳维诚

王之涣的“更上一层楼”已经成为不断探索者的座右铭．不管楼层有多高，登楼的阶梯总是有限的．当你登上了第一级，就可以把第一级作为攀登第二级的基础，如果不先登上第一级，就无法登上第二级．同理，如果登上了第ｎ级，你不因难而退，坚持继续攀登，你就可以用这第ｎ级作为基础，通过努力攀登到第ｎ＋１级．如此不断地从第ｎ级攀登到第ｎ＋１级，就一定可以逐步攀登到可以“穷千里目”的顶点．

现实中的楼梯是有限的，但是数学家们却想像出一种没有尽头的楼梯．１９５８年英国的《心理学杂志》发表朋斯的文章，论述了这种没有尽头的楼梯．这种楼梯无止境地上升和下降，但仍然保持在同一水平上．荷兰著名画家埃歇尔（１８９８～１９７１）根据朋斯等人的思想作出了一幅题为《上升和下降的楼梯》的画，如图１．即使是无穷无尽的楼梯，从第一级开始，不断地从第ｎ级登上第ｎ＋１级的道理也仍然适用．这个普通的道理，正是数学中的数学归纳法、递推法等的基础．

什么是数学归纳法呢？让我们先作一个粗浅的比喻：

过去行军打仗，指挥部每天都要发布一个“口令”作为内部联系的暗号．现在有一支成单行前进的很长很长的队伍，指挥员把“口令”传给走在队伍最前面的第一个人，并且规定了每一个听到了“口令”的人，都必须把“口令”准确无误地传达给紧跟在他后面的一个人．于是，“口令”将会从第一个人传给第二个，第二个人传给第三个，如此继续下去，不管这支队伍有多长，兵员有多少，最终每一个人都可得到“口令”．这就是数学归纳法的思想．

例如下面的“的士发票”问题，就是运用数学归纳法解题的例子：

某城市出租汽车的起价是８元，以后按每０．５公里收费１元计算（不足０．５公里的按０．５公里计算），因此，的士的计费表上的元数ｎ，可能出现不小于８的任何一个整数（在理论上是如此，实际中ｎ不可能无限大），但的士公司只印制了两种面值的固定发票，一种是３元的，一种是５元的．不管乘客乘车的计费是多少，都可以用这两种发票抵足他所付车费．你能证明吗？

事实上，乘客乘车的起价是８元，可以用１张３元的和１张５元的发票结清．如果他的车费是ｎ元时可以用这两种发票结清，那么当车费是ｎ＋１元时，也一定可以用这两种发票结清．为什么呢？因为ｎ元可以用这两种发票支付，如果在ｎ元的支付方式中，有５元的发票，那么只要把１张５元的发票换成２张３元的，就得到了ｎ＋１元．如果在ｎ元的支付方式中，没有５元的发票，就至少有３张３元的发票，用２张５元发票换掉３张３元发票，也得到ｎ＋１元．这就是说，我们证明了：如果ｎ元可用两种发票结清，那些ｎ＋１元也一定可用两种发票结清．现在已知８元可用两种发票结清．如此继续，就说明了，任意多元的车费都是可用这两种发票结清的．

又例如，下面的“猜帽子问题”，也是数学归纳法思想的运用．

有一位老师想检测一下他的学生哪一个最聪明．他有ｎ个学生，这ｎ个学生智商都很高，分析推理能力极强．于是老师准备了ｎ－１顶黑色的帽子和若干顶白色的帽子，这些帽子除了颜色不同之外其他都一样，戴帽者如果事先没有看见颜色的话，仅凭自己的感觉是无法判断帽子是哪种颜色的．

老师令ｎ个同学成一行坐在一个阶梯式的教室里，请他们闭上眼睛，老师给每人戴上一顶帽子，然后请大家睁开眼睛，猜一猜自己戴的是什么颜色的帽子．

结果出人意料的事发生了：尽管这些学生都很聪明，而且坐在后面的学生又都能清楚地看到前面的学生戴什么颜色的帽子，但除了最前面的那个学生外，其余的人都不能猜出自己头上戴的是什么颜色的帽子．倒是最前面的人虽然看不见任何人所戴的帽子，却正确地猜出了自己戴的是白色帽子．

请想一想这是什么道理呢？

我们不妨把这ｎ个学生从后往前依次编号为Ａ_１，Ａ_２，…，Ａ_ｎ·先说Ａ_１，因为他很聪明，如果他看见前面ｎ－１学生的帽子都是黑色的，因为黑色帽子只有ｎ－１顶，他一定能断定自己戴的是白色帽子．现在他既然不能断定，肯定在前面ｎ－１个人中有人戴着白帽子．

Ａ_１的思维活动，又给Ａ_２的分析提供了基础．Ａ_２也是高智商的，当然了解Ａ_１的想法．如果Ａ_２前面的人都戴黑帽子，那么Ａ_１看见的戴白帽子的人，一定非Ａ_２莫属了．Ａ_２就会猜出自己戴的是白帽子，可见，Ａ_２前面也有戴白帽子的人．

类似的推理可以继续下去，Ａ_１前面有戴白帽的→Ａ_２前面也有戴白帽的→Ａ_３前面也有戴白帽的→…→Ａ_ｎ－１前面也有戴白帽的．

所以，Ａ_ｎ能猜出自己戴的是白帽．

下面再谈递推问题．

我们仍旧拿登楼的问题作为例子来说明递推的思想．

小明要登上一共有ｎ级的楼梯，他每一步可以跨上一级或两级，试问他登上楼梯有多少种不同的方式？