第六章遞推關(guān)系計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院吉林大學(xué)第1頁(yè)主要內(nèi)容§6.1遞推關(guān)系建立§6.2常系數(shù)線性齊次遞推關(guān)系求解§6.3常系數(shù)線性非齊次遞推關(guān)系求解§6.4用生成函數(shù)求解遞推關(guān)系§6.5用迭代和歸納法求解遞推關(guān)系第2頁(yè)§6.1遞推關(guān)系建立錯(cuò)排數(shù)Dn遞推關(guān)系

第3頁(yè)Stirling數(shù)遞推關(guān)系:S2（n+1,k)=S2(n,k-1)+k*S2(n,k)第三章性質(zhì)3.5.1第4頁(yè)定義6.1

給定一個(gè)數(shù)列H(0),H(1),…,H(n),…

若存在整數(shù)n0，使當(dāng)n≥n0時(shí)，能夠用等號(hào)（或大于號(hào)，小于號(hào)）將H(n)與其前面一些項(xiàng)H(i)，0≤i≤n，聯(lián)絡(luò)起來(lái)式子叫做一個(gè)遞推關(guān)系。遞推關(guān)系(用等號(hào))也稱(chēng)遞歸關(guān)系，遞歸方程。

第5頁(yè)從本質(zhì)上講，遞推關(guān)系是研究整變量函數(shù)或者說(shuō)是研究數(shù)列，與此對(duì)應(yīng)是連續(xù)論域中微分方程。所以，我們能夠類(lèi)似方法對(duì)它們進(jìn)行研究。

第6頁(yè)f(n)代表了某個(gè)組累計(jì)數(shù)問(wèn)題解，所以遞推關(guān)系是組累計(jì)數(shù)主要工具求出序列通項(xiàng)表示式f(n)求不出f(n)顯式，能夠計(jì)算出f(n)值或者范圍第7頁(yè)遞推關(guān)系慣用求解方法（1）特征根法；(§6.2,§6.3)（2）迭代法和歸納法；(§6.5)（3）生成函數(shù)法；（§6.4）第8頁(yè)例6.1.2Fibonacci數(shù)列問(wèn)題是一個(gè)古老數(shù)學(xué)問(wèn)題，是于1202年提出。問(wèn)題表述以下:把一對(duì)兔子（雌、雄各一只）在某年開(kāi)始放到圍欄中，每個(gè)月這對(duì)兔子都生出一對(duì)新兔，其中雌、雄各一只。由第二個(gè)月開(kāi)始，每對(duì)新兔每個(gè)月也生出一對(duì)新兔，也是雌、雄各一只。問(wèn)n個(gè)月后圍欄中有多少對(duì)兔子？這是一個(gè)數(shù)學(xué)模型形象表示，不能真正用來(lái)表示兔子繁殖規(guī)律。第9頁(yè)棋盤(pán)覆蓋問(wèn)題，用多米諾骨牌（能夠看成一個(gè)2×1大小方格）完全覆蓋一個(gè)2×n棋盤(pán)。覆蓋方案數(shù)等于Fibonacci數(shù)f(n).另外一個(gè)例子，也表達(dá)出遞推關(guān)系思想：例6.1.1有n級(jí)臺(tái)階，某人從下向上走，若每次只能跨1級(jí)或者2級(jí)，問(wèn)他從地面走到第n級(jí)有多少種不一樣方法?甚至是更詳細(xì)問(wèn)題，比如n=10.第10頁(yè)例6.1.3（Hanoi塔問(wèn)題）現(xiàn)有A，B，C三根立柱以及n個(gè)大小不等中空?qǐng)A盤(pán)，這些圓盤(pán)自小到大套在A柱上形成塔形，如圖6.1.1所表示，要把n個(gè)圓盤(pán)從A柱上搬到C柱上，并保持原來(lái)次序不變，要求每次只能從一根立柱上拿下一個(gè)圓盤(pán)放在另一根立柱上，且不允許大盤(pán)壓在小盤(pán)上，問(wèn)最少要搬多少次？

第11頁(yè)第12頁(yè)

解：記f(n)為n個(gè)圓盤(pán)從A柱搬到C柱所需最小次數(shù).整個(gè)搬運(yùn)過(guò)程可分成三個(gè)階段；（1）將套在A柱上面n-1個(gè)圓盤(pán)從A柱按要求搬到B柱，搬動(dòng)次數(shù)為f(n-1);（2）把A柱上最下面那個(gè)圓盤(pán)搬到C柱上，搬動(dòng)次數(shù)為1;（3）把B柱上n-1個(gè)圓盤(pán)按要求搬到C柱上，搬動(dòng)次數(shù)為f(n-1);由加法標(biāo)準(zhǔn)知，f(n)=2f(n-1)+1又顯然f(1)=1，所以有以下帶有初值遞推關(guān)系:

f(n)=2f(n-1)+1f(1)=1

第13頁(yè)則稱(chēng)作k階常系數(shù)線性齊次遞推關(guān)系(6.2.1)定義6.2.1設(shè)k是給定正整數(shù)，若數(shù)列相鄰k+1項(xiàng)間滿足關(guān)系:假如滿足下面三個(gè)條件都是常數(shù)

第14頁(yè)(6.2.2)

假如有一個(gè)數(shù)列代入遞推關(guān)系（6.2.1），使得其對(duì)任何n≥k都成立，則稱(chēng)這個(gè)數(shù)列是遞推關(guān)系（6.2.1）解。

常系數(shù)線性齊次遞推關(guān)系普通形式為

第15頁(yè)定義6.2.2方程

(6.2.2)

叫做遞推關(guān)系(6.2.2)特征方程，它k個(gè)根q1，q2……qk叫做該遞推關(guān)系特征根。其中qi(i=1,2,…,k)是復(fù)數(shù)。§6.2常系數(shù)線性齊次遞推關(guān)系求解

特征根法第16頁(yè)(一)無(wú)重特征根引理6.2.1

設(shè)q是一個(gè)非零復(fù)數(shù)，則f(n)＝qn是遞推關(guān)系(6.2.2)一個(gè)解當(dāng)且僅當(dāng)q是它一個(gè)特征根。引理6.2.2設(shè)h1(n)和h2(n)是遞推關(guān)系(6.2.2)兩個(gè)解，b1和b2是任意常數(shù)，則b1h1(n)＋b2h2(n)也是遞推關(guān)系(6.2.2)解。第17頁(yè)定義6.2.3

假如對(duì)于遞推關(guān)系(6.2.2)每個(gè)解h(n)都能夠選擇一組常數(shù)c1’，c2’，c3’，……ck’,使得h(n)＝c1’q1n＋c2’q2n＋……＋ck’qkn成立，則稱(chēng)b1q1n＋b2q2n＋……＋bkqkn是遞推關(guān)系通解，其中b1b2……bk為任意常數(shù)。第18頁(yè)定理6.2.1

設(shè)q1，q2，……qk是遞推關(guān)系(6.2.2)k個(gè)不相等特征根，則

f(n)＝b1q1n＋b2q2n＋……＋bkqkn是遞推關(guān)系(6.2.2)通解.第19頁(yè)例6.2.1求解關(guān)于Fibonacci數(shù)遞推關(guān)系第20頁(yè)第21頁(yè)第22頁(yè)第23頁(yè)例6.2.2求解遞推關(guān)系

第24頁(yè)第25頁(yè)第26頁(yè)(二)有重特征根定理6.2.2設(shè)q1，q2，……qt是遞推關(guān)系(6.2.2)不相等特征根，ei是qi重?cái)?shù),則遞推關(guān)系(6.2.2)通解

f(n)=f1(n)+f2(n)+……+ft(n)其中第27頁(yè)例6.2.4求解遞推關(guān)系第28頁(yè)對(duì)第29頁(yè)對(duì)通解為解方程組，得c1=5,c2=2,c3=-4所以原遞推關(guān)系解為f（n)=5*2n+2n*2n-4*3n第30頁(yè)補(bǔ)例求解遞推關(guān)系第31頁(yè)(一)普通形式§6.3常系數(shù)線性非齊次遞推關(guān)系求解(6.3.1)(6.3.2)

對(duì)應(yīng)齊次遞推關(guān)系為

第32頁(yè)定理6.3.1

k階常系數(shù)線性非齊次遞推關(guān)系（6.3.1）通解是遞推關(guān)系（6.3.1）特解加上其對(duì)應(yīng)齊次遞推關(guān)系（6.3.2）通解。

第33頁(yè)對(duì)于普通g(n)沒(méi)有普遍解法，只對(duì)一些簡(jiǎn)單情況能夠用待定系數(shù)法求f*(n)

。第34頁(yè)例6.3.1求解遞推關(guān)系

第35頁(yè)比較等式兩邊解：因?yàn)?不是特征方程根，所以該遞推關(guān)系非齊次特解為，將其代入遞推關(guān)系，得系數(shù)，得

從而a=2.第36頁(yè)而對(duì)應(yīng)齊次遞推關(guān)系通解為由定理6.3.1知，非齊次遞推關(guān)系通解為

由初值得從而

故第37頁(yè)例6.3.2

求解遞推關(guān)系解因?yàn)?是特征方程根，所以該遞推關(guān)系特解為

將它代入遞推關(guān)系，得到a=6第38頁(yè)從而非齊次遞推關(guān)系通解為再由初值求得于是第39頁(yè)