高中數(shù)學(xué)：第三章：數(shù)列-遞推法解題（競賽精講）

1、§3.3遞推法解題基礎(chǔ)知識(shí) 對于某些與自然數(shù)有關(guān)的問題，我們有時(shí)可以用遞推法解決，扎謂用遞推法解題，就是根據(jù)題目的特點(diǎn)，構(gòu)造出遞推關(guān)系解題的一種方法，解決問題的關(guān)鍵在于構(gòu)造遞推關(guān)系。遞推關(guān)系一般可以用歸納、猜想等途徑獲得。利用遞推法解題的一般步驟為：(1)確定初始值；(2)建立遞推關(guān)系；(3)利用遞推關(guān)系求通項(xiàng)。遞推方法是人們從開始認(rèn)識(shí)數(shù)量關(guān)系時(shí)就很自然地產(chǎn)生的一種推理思想.例如自然數(shù)中最小的數(shù)是1，比1大1的數(shù)是2，接下來比2大1的數(shù)是3，由此得到了自然數(shù)數(shù)列：1，2，3，4，5，.在這里實(shí)際上就有了一個(gè)遞推公式，假設(shè)第n個(gè)數(shù)為an，則an+1=an+1;即由自然數(shù)中第n個(gè)數(shù)加上1

2、，就是第n+1個(gè)數(shù)。由此可得an2=an11，這樣就可以得到自然數(shù)數(shù)列中任何一個(gè)數(shù).再看一個(gè)例子：平面上5條直線最多能把圓的內(nèi)部分成幾部分？平面上100條直線最多能把圓的內(nèi)部分成幾部分？解：假設(shè)用ak表示k條直線最多能把圓的內(nèi)部分成的部分?jǐn)?shù).這里k0，1，2，.a01a1=a0+12a2=a12=4a3=a23=7a4=a3+411歸納出遞推公式an1an+n. （1）即畫第n1條直線時(shí)，最多增加n部分.原因是這樣的：第一條直線最多把圓分成兩部分，故a12.當(dāng)畫第二條直線時(shí)要想把圓內(nèi)部分割的部分盡可能多，就應(yīng)和第一條直線在圓內(nèi)相交，交點(diǎn)把第二條直線在圓內(nèi)部分分成兩條線段，而每條線段又把原來的一

3、個(gè)區(qū)域劃分成兩個(gè)區(qū)域，因而增加的區(qū)域數(shù)是2，正好等于第二條直線的序號(hào).同理，當(dāng)畫第三條直線時(shí)，要想把圓內(nèi)部分割的部分?jǐn)?shù)盡可能多，它就應(yīng)和前兩條直線在圓內(nèi)各有一個(gè)交點(diǎn).兩個(gè)交點(diǎn)把第三條線在圓內(nèi)部分成三條線段.而每條線段又把原來一個(gè)區(qū)域劃分成兩個(gè)區(qū)域.因而增加的區(qū)域部分?jǐn)?shù)是3，正好等于第三條直線的序號(hào)，.這個(gè)道理適用于任意多條直線的情形.所以遞推公式（1）是正確的.這樣就易求得5條直線最多把圓內(nèi)分成：a5=a4+511=516（部分）。要想求出100條直線最多能把圓內(nèi)分成多少區(qū)域，就去求通項(xiàng)公式。一般來說，如果一個(gè)與自然數(shù)有關(guān)的數(shù)列中的任一項(xiàng)an可以由它前面的k（n-1）項(xiàng)經(jīng)過運(yùn)算或其他方法表示出

4、來，我們就稱相鄰項(xiàng)之間有遞歸關(guān)系，并稱這個(gè)數(shù)列為遞歸數(shù)列.如果這種推算方法能用公式表示出來，就稱這種公式為遞推公式或遞推關(guān)系式.通過尋求遞歸關(guān)系來解決問題的方法就稱為遞推方法. 許多與自然數(shù)有關(guān)的數(shù)學(xué)問題都常常具有遞推關(guān)系，可以用遞推公式來表達(dá)它的數(shù)量關(guān)系.如何尋求這個(gè)遞推公式是解決這類問題的關(guān)鍵之一，常用的方法是“退”到問題最簡單情況開始觀察.逐步歸納并猜想一般的速推公式.在小學(xué)生階段，我們僅要求學(xué)生能撥開問題的一些表面現(xiàn)象由簡到繁地歸納出問題的遞推公式就行了，不要求嚴(yán)格證明.當(dāng)然能證明更好.所謂證明，就是要嚴(yán)格推出你建立的關(guān)系式適合所有的n，有時(shí)，僅僅在前面幾項(xiàng)成立的關(guān)系式，不一定當(dāng)n較大

5、時(shí)也成立。1、 “河內(nèi)塔問題”傳說在印度的佛教圣地貝拿勒斯圣廟里安放著個(gè)一個(gè)黃銅板，板上插著三根寶石針，在第一根寶石針上，從下到上穿著由大到小的64片中心有孔的金片.每天都有一個(gè)值班僧侶按下面規(guī)則移動(dòng)金片：把金片從第一根寶石針移到其余的某根寶石針上.要求一次只能移動(dòng)一片，而且小片永遠(yuǎn)要放在大片的上面.當(dāng)時(shí)傳說當(dāng)64片金片都按上面的規(guī)則從第一根寶石針移到另一根寶石針上時(shí)，世界將在一聲霹靂中毀滅.所以有人戲稱這個(gè)問題叫“世界末日”問題（也稱為“Hanoi塔”問題），當(dāng)然，移金片和世界毀滅并無聯(lián)系，這只是一個(gè)傳說而已，但說明這是一個(gè)需要移動(dòng)很多很多次才能辦到的事情.解這個(gè)問題的方法在算法分析中也常用

6、到.究竟按上述規(guī)則移動(dòng)完成64片金片需要移動(dòng)多少次呢？將此問題一般化為：設(shè)有個(gè)銀圈，大小不同，從大到小排列在三根金棒中的一根。這些銀圈要搬到另一根金棒上，每次搬一個(gè)。第三根金棒作為銀圈暫時(shí)擺放用。在搬動(dòng)過程中，仍要保持大圈在下，小圈在上，問要搬動(dòng)多少次，才能將所有銀圈從一根棒搬到另一根，且搬完后銀圈相對位置不變？思路：尋找與前面各項(xiàng)之間的關(guān)系，由題設(shè)條件列出等式。解：令用表所求的搬動(dòng)次數(shù)，把第一棒個(gè)銀圈的個(gè)搬到第三棒，再將最大一個(gè)銀圈搬到第二棒，然后又將第三棒上的個(gè)圈搬到第二棒上，如此繼續(xù)，可完成這次搬動(dòng)任務(wù)。因?yàn)榘醾€(gè)銀圈從一棒到另一棒需次，故可得遞推式。下面對遞推式的求解。最后，可得。典例分

7、析例1用100元人民幣購買物品，規(guī)定每天只能用以下三種方式之一購買物品： (1)買甲物品1元；(2)買乙物品2元；(3)買丙物品2元 而且規(guī)定不允許不買物品。試問有多少種方式花完這100元錢？例2有一種用硬幣下棋的游戲，棋盤上標(biāo)有第0站，第1站，第2站，第100站。一枚棋子開始在第0站，棋手每擲一次硬幣，棋子跳動(dòng)一次：若擲出的是正面，棋子向前跳兩站，若擲出的是反面，則棋子向前跳一站，直到棋子恰好跳到第99站(勝利大本營)或第100站(失敗大本營)時(shí)，游戲結(jié)束。如果硬幣出現(xiàn)正反面的概率都是，分別求棋子跳到勝利大本營與失敗大本營的概率。例3現(xiàn)有四個(gè)人做傳球游戲，要求接球后馬上傳給別人。由甲先傳球，并作為第1次傳球，求經(jīng)過10次傳球仍回到發(fā)球人甲手中的傳球方式的種數(shù)。例4(Bernoulli-Euler裝錯(cuò)信問題)某人寫了n封信，并在每個(gè)信封上寫下了對應(yīng)的地址和收信人的姓名。問：將所有的信都錯(cuò)信封的情況共有多少種？例5現(xiàn)將n邊形的邊依次記為，每條邊都涂上紅、黃、綠三種顏色中的一種，要使相鄰兩邊的顏色互不相同，有多少種不同的涂色方法？例6(第五屆西部競賽題)已知可以表示成為變元的二次多項(xiàng)式，求這個(gè)多項(xiàng)式的系數(shù)之和。例7已知函數(shù)，數(shù)列是公差為等差數(shù)列，數(shù)列為公比為的等比數(shù)列，且，；，。設(shè)數(shù)列對于任意的正整數(shù)n都有成立，