2、}的遞推方程.當(dāng)給定遞推方程和適當(dāng)?shù)某踔稻臀ㄒ淮_定了序列.例如，F(xiàn)ibonacci數(shù)列：1，1，2，3，5，8，…，記作{fn}.遞推方程fn=fn?1+fn?2初值f0=1，f1=1階乘計(jì)算數(shù)列：1，2，6，24，5！，…,記作{F(n)}遞推方程F(n)=nF(n?1)初值F(1)=14化簡得an=6an?1+8n?1,可以解得an=(6n+8n)/2遞推方程的實(shí)例——計(jì)數(shù)編碼例1一個(gè)編碼系統(tǒng)用八進(jìn)制數(shù)字對信息編碼，一個(gè)碼是有效的當(dāng)且僅當(dāng)含有偶數(shù)個(gè)7,求n位長的有效碼字有多少個(gè)？解設(shè)所求有效碼字為an個(gè).
3、分類處理、分步處理得到遞推方程和初值如下：an=7an?1+8n?1?an?1a1=75遞推方程的實(shí)例——Hanoi塔例2從A柱將這些圓盤移到C柱上去.如果把一個(gè)圓盤從一個(gè)柱子移到另一個(gè)柱子稱作一次移動(dòng)，在移動(dòng)和放置時(shí)允許使用B柱，但不允許大圓盤放到小圓盤的上面.問把所有的圓盤的從A移到C總計(jì)需要多少次移動(dòng)？初值是T(1)=1可證明解是T(n)=2n?1移動(dòng)n個(gè)盤子的總次數(shù)為T(n).因此得到遞推方程T(n)=2T(n?1)+1.6遞推方程的實(shí)例——算法分析例3哪種排序算法在最壞情況下復(fù)雜度比較低？插入排序，
4、歸并排序插入排序W(n)=W(n?1)+n?1W(1)=0解得W(n)=O(n2).歸并排序，不妨設(shè)n=2k.W(n)=2W(n/2)+n－1W(1)=0解得W(n)=O(nlogn)7常系數(shù)線性齊次遞推方程求解其中a1,a2,…,ak為常數(shù)，ak?0稱為k階常系數(shù)線性齊次遞推方程b0,b1,…,bk?1為k個(gè)初值實(shí)例：Fibonacci數(shù)列的遞推方程定義10.2常系數(shù)線性齊次遞推方程的標(biāo)準(zhǔn)形：8常系數(shù)線性齊次遞推方程 的公式解法特征方程、特征根遞推方程的解與特征根的關(guān)系解的線性性質(zhì)無重根下通解的結(jié)構(gòu)求解實(shí)例
5、有重根下通解的結(jié)構(gòu)求解實(shí)例9特征方程與特征根定義10.3特征方程xk?a1xk?1?…?ak=0，特征方程的根稱為遞推方程的特征根實(shí)例：遞推方程fn=fn?1+fn?2特征方程x2?x?1=0特征根10遞推方程解與特征根的關(guān)系定理10.1設(shè)q是非零復(fù)數(shù)，則qn是遞推方程的解當(dāng)且僅當(dāng)q是它的特征根.證qn是遞推方程的解?qn?a1qn?1?a2qn?2?…?akqn?k=0?qn?k(qk?a1qk?1?a2qk?2?…?ak)=0?qk?a1qk?1?a2qk?2?…?ak=0?q是它的特征根注：這里遞推方程
6、指常系數(shù)線性齊次遞推方程11解的線性性質(zhì)定理10.2設(shè)h1(n)和h2(n)是遞推方程的解，c1,c2為任意常數(shù)，則c1h1(n)+c2h2(n)也是這個(gè)遞推方程的解.證將c1h1(n)+c2h2(n)代入該遞推方程進(jìn)行驗(yàn)證.推論若q1,q2,…,qk是遞推方程的特征根，則c1q1n+c2q2n+…+ckqkn是該遞推方程的解，其中c1,c2,…,ck是任意常數(shù).注：這里的遞推方程指的是常系數(shù)線性齊次遞推方程12無重根下通解的結(jié)構(gòu)定義10.4若對常系數(shù)線性齊次遞推方程的每個(gè)解h(n)都存在一組常數(shù)c1?,c2
7、?,…,ck?使得h(n)=c1?q1n+c2?q2n+…+ck?qkn成立，則稱c1q1n+c2q2n+…+ckqkn為該遞推方程的通解定理10.3設(shè)q1,q2,…,qk是常系數(shù)線性齊次遞推方程不等的特征根，則H(n)=c1q1n+c2q2n+…+ckqkn為該遞推方程的通解.13定理的證明證：H(n)是解.設(shè)h(n)是遞推方程的任意解，h(0),h(1),…,h(k?1)由初值b0,b1,…,bk?1唯一確定.代入方程得到方程組系數(shù)行列式當(dāng)qi?qj時(shí)，方程組有唯一解14求解實(shí)例例4Fibonacci數(shù)列
8、：fn=fn?1+fn?2，特征根為通解為代入初值f0=1,f1=1,得解得解是15有重根下求解中的問題例5解特征方程x2?4x+4=0通解H(n)=c12n+c22n=c2n代入初值得：c無解.問題：兩個(gè)解線性相關(guān)16有重根下的通解結(jié)構(gòu)定理10.4設(shè)q1,q2,…,qt是遞推方程的不相等的特征根，且qi的重?cái)?shù)為ei，i=1,2,…,t，令那么通解17求解實(shí)例例6求解以下遞推方程其中待定常數(shù)滿足以下
