奧數(shù)專題之遞推

1、1奧數(shù)專題之遞推奧數(shù)專題之遞推遞推法專題遞推法是組合數(shù)學(xué)中的一個重要解題方法，許多問題通過遞推法來解決就顯得精巧簡捷鑒于這一方法在學(xué)習(xí)中的應(yīng)用越來越廣泛，掌握和運用這種方法，就顯得更加重要遞推方法問題主要有兩類：一是問題中有明顯的遞推關(guān)系，重點在于遞推關(guān)系的應(yīng)用；二是問題中沒有明顯的遞推關(guān)系，需要對已有條件進(jìn)行變形或改變問題的有關(guān)形式而建立遞推關(guān)系，將問題轉(zhuǎn)化為第一類問題。本文重點探索第二類問題。通過建立、研究遞推關(guān)系Sk1=f(Sk)

2、，使問題得以解決的方法稱為遞推方法。例1平面上有n條直線，它們中任意兩條都不平行，且任意三條都不交于一點。這n條直線可以把平面分割成多少個部分？請看一個引起普遍關(guān)注的關(guān)于世界末日的問題。例2有這樣一段關(guān)于“世界末日”的傳說。在印度北部的一個佛教的圣廟里，桌上的黃銅板上，放著三根寶石針，每根長約0.5米。據(jù)說印度教的主神梵天在創(chuàng)造世界時，在其中的一根針上，自上而下由小到大放了六十四片金片。每天二十四小時內(nèi)，都有僧侶值班，按照以下的規(guī)律，不

3、停地把這些金片在三根寶石針上移來移去：每次只準(zhǔn)移動一片，且不論在那根針上，較小的金片只能放在較大的金片上。當(dāng)所有六十四片金片都從梵天創(chuàng)造世界時所放的那根針上移到另一根針上時，世界的末日就要到來。這雖是一個傳說，但卻引起人們的重視，大家都想知道僧侶移動完畢這六十四片金片需要多少時間。也就是說，人類在這個世界上還可以生存多少時間。例3有10級臺階，小王從下向上走，若每次只能跨一級或兩級，他走上去共有多少種不同的走法？追問追問：10級的情況可

4、以一一列出，臺階數(shù)比較多的情況，怎么辦？提示：此即為斐波那契數(shù)列an求通項的問題。例4同室4人各寫一張賀年卡，先集中起來，然后每人從中拿一張別人送出的賀年卡，則4張賀年卡不同的分配方式共有()（A）6種（B）9種（C）11種（D）23種這里，我們引進(jìn)一個概念：設(shè)a1a2a3…，an是1，2，3，…，n的一個排列如果aii(i=12…，n)則稱這?種排列為一個錯位排列（也稱為更列）。3遞推數(shù)列求通項問題遞推數(shù)列求通項問題一、一、引例引例—

5、—斐波那契數(shù)列斐波那契數(shù)列假定一對兔子每隔一個月生一對一雌一雄的小兔子，每對小兔在兩個月以后也開始生一對一雌一雄的小兔子，隔月一次。年初時兔房里有一對小兔（一雌一雄），問一年以后，兔房里有多少對兔子？解：設(shè)第個月初時兔房里有兔子對。易知nnf………(1)211321???fff第個月初時兔房里的兔子可分為兩部分：一部分是第個月初時已經(jīng)在兔房2?n1?n里的兔子，共有對，另一部分是第個月初時新出生的小兔，共有對，于是1?nf2?nnf……

6、…………..(2)nnnfff????12這就是為廣大中小學(xué)生所熟悉的斐波那契數(shù)列，它是遞推數(shù)列的一個典型代表。二、遞推數(shù)列二、遞推數(shù)列（一）.遞推數(shù)列的定義斐波那契數(shù)列是遞推數(shù)列的典型代表，其中(2)式稱為遞推式，也稱遞推關(guān)系，(1)式是初始條件，這二者是遞推數(shù)列的必要構(gòu)成條件。一般地，我們把滿足………………………..(6))...(11?????knnnknfffFf和初始值的數(shù)列稱為階遞推數(shù)列。當(dāng)遞推關(guān)系的形式為nfk………………

7、…………(7))(...2211nFfcfcfcfnkknknkn??????????時，數(shù)列稱為階常系數(shù)線性遞推數(shù)列，其中為常數(shù)，且。若函數(shù)nfkkccc...210?kc，則遞推關(guān)系(7)所確定的數(shù)列稱為階常系數(shù)齊次線性遞推數(shù)列；否則，0)(?nFnfk稱遞推關(guān)系(7)所確定的數(shù)列為階常系數(shù)非齊次線性遞推數(shù)列。因此，斐波那契數(shù)列nfk是一個2階常系數(shù)齊次線性遞推數(shù)列。遞推數(shù)列是數(shù)列中的一個重要類型，數(shù)學(xué)競賽中的數(shù)列問題多與遞推數(shù)列尤