數(shù)學(xué)中的歸納與遞推

歐陽(yáng)維誠(chéng)

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

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

什么是數(shù)學(xué)歸納法呢？讓我們先作一個(gè)粗淺的比喻：

過去行軍打仗，指揮部每天都要發(fā)布一個(gè)“口令”作為內(nèi)部聯(lián)系的暗號(hào)．現(xiàn)在有一支成單行前進(jìn)的很長(zhǎng)很長(zhǎng)的隊(duì)伍，指揮員把“口令”傳給走在隊(duì)伍最前面的第一個(gè)人，并且規(guī)定了每一個(gè)聽到了“口令”的人，都必須把“口令”準(zhǔn)確無(wú)誤地傳達(dá)給緊跟在他后面的一個(gè)人．于是，“口令”將會(huì)從第一個(gè)人傳給第二個(gè)，第二個(gè)人傳給第三個(gè)，如此繼續(xù)下去，不管這支隊(duì)伍有多長(zhǎng)，兵員有多少，最終每一個(gè)人都可得到“口令”．這就是數(shù)學(xué)歸納法的思想．

例如下面的“的士發(fā)票”問題，就是運(yùn)用數(shù)學(xué)歸納法解題的例子：

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

事實(shí)上，乘客乘車的起價(jià)是８元，可以用１張３元的和１張５元的發(fā)票結(jié)清．如果他的車費(fèi)是ｎ元時(shí)可以用這兩種發(fā)票結(jié)清，那么當(dāng)車費(fèi)是ｎ＋１元時(shí)，也一定可以用這兩種發(fā)票結(jié)清．為什么呢？因?yàn)椋钤梢杂眠@兩種發(fā)票支付，如果在ｎ元的支付方式中，有５元的發(fā)票，那么只要把１張５元的發(fā)票換成２張３元的，就得到了ｎ＋１元．如果在ｎ元的支付方式中，沒有５元的發(fā)票，就至少有３張３元的發(fā)票，用２張５元發(fā)票換掉３張３元發(fā)票，也得到ｎ＋１元．這就是說(shuō)，我們證明了：如果ｎ元可用兩種發(fā)票結(jié)清，那些ｎ＋１元也一定可用兩種發(fā)票結(jié)清．現(xiàn)在已知８元可用兩種發(fā)票結(jié)清．如此繼續(xù)，就說(shuō)明了，任意多元的車費(fèi)都是可用這兩種發(fā)票結(jié)清的．

又例如，下面的“猜帽子問題”，也是數(shù)學(xué)歸納法思想的運(yùn)用．

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

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

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

請(qǐng)想一想這是什么道理呢？

我們不妨把這ｎ個(gè)學(xué)生從后往前依次編號(hào)為Ａ_１，Ａ_２，…，Ａ_ｎ·先說(shuō)Ａ_１，因?yàn)樗苈斆?，如果他看見前面ｎ－１學(xué)生的帽子都是黑色的，因?yàn)楹谏弊又挥校睿表?，他一定能斷定自己戴的是白色帽子．現(xiàn)在他既然不能斷定，肯定在前面ｎ－１個(gè)人中有人戴著白帽子．

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

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

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

下面再談遞推問題．

我們?nèi)耘f拿登樓的問題作為例子來(lái)說(shuō)明遞推的思想．

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

我們用ａｉ表示小明登上第ｉ級(jí)樓梯的不同方式數(shù)．這樣就得到一個(gè)數(shù)列：

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

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

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

現(xiàn)在我們來(lái)看登上第ｎ級(jí)的方式數(shù)．要登上第ｎ級(jí)有兩種情況：

第一種先登上了第ｎ－１級(jí)，然后一步跨一級(jí)到達(dá)第ｎ級(jí)

第二種先登上了第ｎ－２級(jí)，然后一步跨兩級(jí)到達(dá)第ｎ級(jí)．

因?yàn)榈巧系冢睿布?jí)有ａ_ｎ－２種不同的方式，登上第ｎ－１級(jí)有ａ_ｎ－１種方式，所以ａ_ｎ＝ａ_ｎ－２＋ａ_ｎ－１．于是我們就得到了遞推關(guān)系和初始條件：

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

根據(jù)（２）式可以逐個(gè)算出每個(gè)ａ_ｉ：

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

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

……

通過遞推可算出數(shù)列（１）的各項(xiàng)依次是：

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

這個(gè)數(shù)列正是菲波納契數(shù)列．