數學中的歸納與遞推

歐陽維誠

王之渙的“更上一層樓”已經成為不斷探索者的座右銘．不管樓層有多高，登樓的階梯總是有限的．當你登上了第一級，就可以把第一級作為攀登第二級的基礎，如果不先登上第一級，就無法登上第二級．同理，如果登上了第ｎ級，你不因難而退，堅持繼續攀登，你就可以用這第ｎ級作為基礎，通過努力攀登到第ｎ＋１級．如此不斷地從第ｎ級攀登到第ｎ＋１級，就一定可以逐步攀登到可以“窮千里目”的頂點．

現實中的樓梯是有限的，但是數學家們卻想像出一種沒有盡頭的樓梯．１９５８年英國的《心理學雜志》發表朋斯的文章，論述了這種沒有盡頭的樓梯．這種樓梯無止境地上升和下降，但仍然保持在同一水平上．荷蘭著名畫家埃歇爾（１８９８～１９７１）根據朋斯等人的思想作出了一幅題為《上升和下降的樓梯》的畫，如圖１．即使是無窮無盡的樓梯，從第一級開始，不斷地從第ｎ級登上第ｎ＋１級的道理也仍然適用．這個普通的道理，正是數學中的數學歸納法、遞推法等的基礎．

什么是數學歸納法呢？讓我們先作一個粗淺的比喻：

過去行軍打仗，指揮部每天都要發布一個“口令”作為內部聯系的暗號．現在有一支成單行前進的很長很長的隊伍，指揮員把“口令”傳給走在隊伍最前面的第一個人，并且規定了每一個聽到了“口令”的人，都必須把“口令”準確無誤地傳達給緊跟在他后面的一個人．于是，“口令”將會從第一個人傳給第二個，第二個人傳給第三個，如此繼續下去，不管這支隊伍有多長，兵員有多少，最終每一個人都可得到“口令”．這就是數學歸納法的思想．

例如下面的“的士發票”問題，就是運用數學歸納法解題的例子：

某城市出租汽車的起價是８元，以后按每０．５公里收費１元計算（不足０．５公里的按０．５公里計算），因此，的士的計費表上的元數ｎ，可能出現不小于８的任何一個整數（在理論上是如此，實際中ｎ不可能無限大），但的士公司只印制了兩種面值的固定發票，一種是３元的，一種是５元的．不管乘客乘車的計費是多少，都可以用這兩種發票抵足他所付車費．你能證明嗎？

事實上，乘客乘車的起價是８元，可以用１張３元的和１張５元的發票結清．如果他的車費是ｎ元時可以用這兩種發票結清，那么當車費是ｎ＋１元時，也一定可以用這兩種發票結清．為什么呢？因為ｎ元可以用這兩種發票支付，如果在ｎ元的支付方式中，有５元的發票，那么只要把１張５元的發票換成２張３元的，就得到了ｎ＋１元．如果在ｎ元的支付方式中，沒有５元的發票，就至少有３張３元的發票，用２張５元發票換掉３張３元發票，也得到ｎ＋１元．這就是說，我們證明了：如果ｎ元可用兩種發票結清，那些ｎ＋１元也一定可用兩種發票結清．現在已知８元可用兩種發票結清．如此繼續，就說明了，任意多元的車費都是可用這兩種發票結清的．

又例如，下面的“猜帽子問題”，也是數學歸納法思想的運用．

有一位老師想檢測一下他的學生哪一個最聰明．他有ｎ個學生，這ｎ個學生智商都很高，分析推理能力極強．于是老師準備了ｎ－１頂黑色的帽子和若干頂白色的帽子，這些帽子除了顏色不同之外其他都一樣，戴帽者如果事先沒有看見顏色的話，僅憑自己的感覺是無法判斷帽子是哪種顏色的．

老師令ｎ個同學成一行坐在一個階梯式的教室里，請他們閉上眼睛，老師給每人戴上一頂帽子，然后請大家睜開眼睛，猜一猜自己戴的是什么顏色的帽子．

結果出人意料的事發生了：盡管這些學生都很聰明，而且坐在后面的學生又都能清楚地看到前面的學生戴什么顏色的帽子，但除了最前面的那個學生外，其余的人都不能猜出自己頭上戴的是什么顏色的帽子．倒是最前面的人雖然看不見任何人所戴的帽子，卻正確地猜出了自己戴的是白色帽子．

請想一想這是什么道理呢？

我們不妨把這ｎ個學生從后往前依次編號為Ａ_１，Ａ_２，…，Ａ_ｎ·先說Ａ_１，因為他很聰明，如果他看見前面ｎ－１學生的帽子都是黑色的，因為黑色帽子只有ｎ－１頂，他一定能斷定自己戴的是白色帽子．現在他既然不能斷定，肯定在前面ｎ－１個人中有人戴著白帽子．

Ａ_１的思維活動，又給Ａ_２的分析提供了基礎． Ａ_２也是高智商的，當然了解Ａ_１的想法．如果Ａ_２前面的人都戴黑帽子，那么Ａ_１看見的戴白帽子的人，一定非Ａ_２莫屬了． Ａ_２就會猜出自己戴的是白帽子，可見，Ａ_２前面也有戴白帽子的人．

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

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

下面再談遞推問題．

我們仍舊拿登樓的問題作為例子來說明遞推的思想．

小明要登上一共有ｎ級的樓梯，他每一步可以跨上一級或兩級，試問他登上樓梯有多少種不同的方式？

我們用ａｉ表示小明登上第ｉ級樓梯的不同方式數．這樣就得到一個數列：

ａ_１，ａ_２，ａ_３，…，ａ_ｎ－１，ａ_ｎ．（１）

先看ａ_１，登上第一級,顯然只有一種方式，即一步跨上一級，所以ａ_１＝１．

再看ａ_２，登上第二級可以有兩種方式：一種是每步跨一級，兩步跨上第二級；一種是一步就跨上第二級，所以ａ_２＝２．

現在我們來看登上第ｎ級的方式數．要登上第ｎ級有兩種情況：

第一種先登上了第ｎ－１級，然后一步跨一級到達第ｎ級

第二種先登上了第ｎ－２級，然后一步跨兩級到達第ｎ級．

因為登上第ｎ－２級有ａ_ｎ－２種不同的方式，登上第ｎ－１級有ａ_ｎ－１種方式，所以ａ_ｎ＝ａ_ｎ－２＋ａ_ｎ－１．于是我們就得到了遞推關系和初始條件：

ａ_ｎ＝ａ_ｎ－２＋ａ_ｎ－１,ａ_１＝１,ａ_２＝２．（２）

根據（２）式可以逐個算出每個ａ_ｉ：

ａ_３＝ａ_１＋ａ_２＝１＋２＝３，

ａ_４＝ａ_２＋ａ_３＝２＋３＝５，

……

通過遞推可算出數列（１）的各項依次是：

１，２，３，５，８，１３，２１，…

這個數列正是菲波納契數列．