奧數(shù)專題之遞推

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

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

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

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

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

6、…………..(2)nnnfff????12這就是為廣大中小學(xué)生所熟悉的斐波那契數(shù)列，它是遞推數(shù)列的一個(gè)典型代表。二、遞推數(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ù)，且。若函數(shù)nfkkccc...210?kc，則遞推關(guān)系(7)所確定的數(shù)列稱為階常系數(shù)齊次線性遞推數(shù)列；否則，0)(?nFnfk稱遞推關(guān)系(7)所確定的數(shù)列為階常系數(shù)非齊次線性遞推數(shù)列。因此，斐波那契數(shù)列nfk是一個(gè)2階常系數(shù)齊次線性遞推數(shù)列。遞推數(shù)列是數(shù)列中的一個(gè)重要類型，數(shù)學(xué)競(jìng)賽中的數(shù)列問(wèn)題多與遞推數(shù)列尤