離散第講遞歸關(guān)系

1、v離散第講遞歸關(guān)系離散第講遞歸關(guān)系第1頁，共30頁。v回顧回顧定義定義3.5：集合集合1，2，3，n的全排列，使得每個數(shù)的全排列，使得每個數(shù)i都不都不在第在第i位上，稱這樣的排列為位上，稱這樣的排列為1，2，3，n的一個的一個錯置錯置。定理定理3.15：集合集合1，2，3，n的錯置的總數(shù)的錯置的總數(shù)(記為記為 Dn)是是 約定約定D0 = =1 。定理定理3.162第第7講講 遞歸關(guān)系遞歸關(guān)系第2頁，共30頁。v回顧回顧 (1) Dn = (n-1)(Dn-2+Dn-1) (2) Dn = nDn-1+(-1)n a1=i ai=1 證.(1) 設(shè)設(shè)1，2，3，n的一個錯置是的一個錯置是a1a

2、2akan ，因為，因為a11，所以，所以a1有有n-1種取種取法。設(shè)法。設(shè)a1=i (2in)，分兩種情況討論：，分兩種情況討論：(1.1) ai=1 。這時取決于其余。這時取決于其余n-2個數(shù)的錯置，這些錯置的數(shù)目是個數(shù)的錯置，這些錯置的數(shù)目是Dn-2 。(1.2) ai1 。這時取決于其余。這時取決于其余n-1個數(shù)的錯置：個數(shù)的錯置：“1不可放置在第不可放置在第i位，其它各數(shù)位，其它各數(shù)j不可放置在第不可放置在第j位位”，這些錯置的數(shù)目是，這些錯置的數(shù)目是Dn-1 。因此，由加法原理和乘法原理因此，由加法原理和乘法原理Dn=(n-1)(Dn-2+Dn-1) 遞歸關(guān)系遞歸關(guān)系3第第7講講

3、遞歸關(guān)系遞歸關(guān)系第3頁，共30頁。vPowerPoint Template_Sub 1計數(shù)基本原理計數(shù)基本原理2排列與組合排列與組合3重集的排列與組合重集的排列與組合4遞歸關(guān)系遞歸關(guān)系4第第7講講 遞歸關(guān)系遞歸關(guān)系第4頁，共30頁。v遞歸關(guān)系Textbook Page 44 to 54離散數(shù)學(xué)離散數(shù)學(xué)第第7 7講講第5頁，共30頁。v內(nèi)容提要內(nèi)容提要遞歸關(guān)系遞歸關(guān)系遞歸關(guān)系的定義和實例遞歸關(guān)系的定義和實例用遞歸關(guān)系構(gòu)造模型用遞歸關(guān)系構(gòu)造模型用遞歸關(guān)系為實際問題建模用遞歸關(guān)系為實際問題建模遞歸關(guān)系的迭代求解遞歸關(guān)系的迭代求解常系數(shù)線性齊次遞歸關(guān)系的求解常系數(shù)線性齊次遞歸關(guān)系的求解 什么是常系數(shù)線

4、性齊次遞歸關(guān)系什么是常系數(shù)線性齊次遞歸關(guān)系常系數(shù)線性齊次遞歸關(guān)系的特征根求解方法常系數(shù)線性齊次遞歸關(guān)系的特征根求解方法6第第7講講 遞歸關(guān)系遞歸關(guān)系第6頁，共30頁。v前言前言有多少個有多少個n位二進制串不包含兩個連續(xù)的位二進制串不包含兩個連續(xù)的0？解：解：令令an表示這樣的表示這樣的n位二進制串數(shù)，位二進制串數(shù)，a1 =2(0,1)a2 =3(00,01,10,11)a3=5 (000,001,010,011,100,101,110,111) (010, 110, 011, 101, 111)an分為以分為以0和以和以1結(jié)尾結(jié)尾兩種情況兩種情況對以對以0結(jié)尾的情況：結(jié)尾的情況：是任何不含是任

5、何不含2個連續(xù)個連續(xù)0的的n2位二進制串加上位二進制串加上10組成組成的，有的，有an-2個個對以對以1結(jié)尾的情況：結(jié)尾的情況：是任何不含是任何不含2個連續(xù)個連續(xù)0的的n1位二進制串加上位二進制串加上1組成的，組成的，有有an-1個個 an = an-1 + an-2這個等式叫做這個等式叫做遞歸關(guān)系遞歸關(guān)系，和初始條件一起唯一地確定了序列，和初始條件一起唯一地確定了序列an。遞歸關(guān)系是求解組合數(shù)學(xué)問題的重要工遞歸關(guān)系是求解組合數(shù)學(xué)問題的重要工具，幾乎在所有的數(shù)學(xué)分支中都有重要具，幾乎在所有的數(shù)學(xué)分支中都有重要應(yīng)用應(yīng)用.許多計數(shù)問題用上一章討論的方法不易求解，許多計數(shù)問題用上一章討論的方法不易求

6、解，但可以通過找到但可以通過找到序列的項之間的關(guān)系序列的項之間的關(guān)系間接求間接求解解.7第第7講講 遞歸關(guān)系遞歸關(guān)系第7頁，共30頁。v遞歸關(guān)系遞歸關(guān)系(recurrence relation)(recurrence relation)定義定義1：關(guān)于序列關(guān)于序列an的的遞歸關(guān)系遞歸關(guān)系是一個等式，它把是一個等式，它把an用序列中排在用序列中排在an前面的一項或多項來表示。如果前面的一項或多項來表示。如果一個序列的項滿足某個遞歸關(guān)系，這個序列就叫做一個序列的項滿足某個遞歸關(guān)系，這個序列就叫做該遞歸關(guān)系的該遞歸關(guān)系的解解(或或通項通項,通項公式通項公式)。8第第7講講 遞歸關(guān)系遞歸關(guān)系第8頁，共

7、30頁。v遞歸關(guān)系舉例遞歸關(guān)系舉例 確定序列確定序列an是否為遞歸關(guān)系是否為遞歸關(guān)系an = 2an-1an-2 (n=2,3,4,)的解，這里的解，這里an =3n，n是非負整數(shù)。若是非負整數(shù)。若an =2n或或an =5呢？呢？解：解：(1)假設(shè)對每一個非負整數(shù)假設(shè)對每一個非負整數(shù)n，an=3n。對對n2，可看出，可看出2an-1an-2 = 23(n-1)-3(n-2) = 6n-6-3n+6 = 3n = anan=3n是該遞歸關(guān)系的解是該遞歸關(guān)系的解(2)假設(shè)對每一個非負整數(shù)假設(shè)對每一個非負整數(shù)n，an=2n。a0=1，a1=2，a2=4，2a1a0 = 22-1 = 3a2an=2

8、n不是該遞歸關(guān)系的解不是該遞歸關(guān)系的解(3)假設(shè)對每一個非負整數(shù)假設(shè)對每一個非負整數(shù)n，an=5。對對n2，有，有2an-1an-2 = 25-5 = 5 = an，因此因此an=5是該遞歸關(guān)系的解是該遞歸關(guān)系的解9第第7講講 遞歸關(guān)系遞歸關(guān)系第9頁，共30頁。v說明說明序列的初始條件說明了在遞歸關(guān)系起作用的首序列的初始條件說明了在遞歸關(guān)系起作用的首項之前的那些項項之前的那些項遞歸關(guān)系和初始條件唯一地確定一個序列遞歸關(guān)系和初始條件唯一地確定一個序列，這，這是因為一個遞歸關(guān)系和初始條件一起提供了這是因為一個遞歸關(guān)系和初始條件一起提供了這個序列的遞歸定義個序列的遞歸定義只要使用足夠多次，序列的任意

9、一項都可以從只要使用足夠多次，序列的任意一項都可以從初始條件開始通過遞歸關(guān)系求出初始條件開始通過遞歸關(guān)系求出但對于某些但對于某些特定類型特定類型的序列，可以有的序列，可以有更好的辦更好的辦法法通過它的遞歸關(guān)系和初始條件來通過它的遞歸關(guān)系和初始條件來計算它的通計算它的通項項10第第7講講 遞歸關(guān)系遞歸關(guān)系第10頁，共30頁。v用遞歸關(guān)系構(gòu)造模型用遞歸關(guān)系構(gòu)造模型 例例3.14 平面上平面上n條直線兩兩相交，且沒有任何三條直條直線兩兩相交，且沒有任何三條直線交于一點，求共有多少個交點？線交于一點，求共有多少個交點？解：解：設(shè)設(shè)n(n2)條直線的交點數(shù)目為條直線的交點數(shù)目為h(n)。如果增加第如果增

10、加第n+1條直線，它將與前條直線，它將與前n條條直線相交產(chǎn)生直線相交產(chǎn)生n個交點個交點h(n+1)=h(n)+n，且已知，且已知h(2)=1。h(n)= h(n-1)+n-1 = h(n-2)+n-2+n-1 = h(n-3)+n-3+n-2+n-1=h(2) +2+3+n-1=1+2+3+n-1= n(n-1)/2證明：證明：用數(shù)學(xué)歸納法證明用數(shù)學(xué)歸納法證明h(n)=n(n-1)/2(n2)歸納基礎(chǔ)：歸納基礎(chǔ)：n=2時，時，h(2)=2(2-1)/2=1，成立，成立歸納推理：歸納推理：假設(shè)假設(shè)n=k(k2)時，時，h(k)=k(k-1)/2。則則h(k+1)= h(k)+k = k(k-1)

11、/2+k = (k(k-1)+2k)/2 = k(k+1)/2歸納完成，結(jié)論成立。歸納完成，結(jié)論成立。11第第7講講 遞歸關(guān)系遞歸關(guān)系第11頁，共30頁。v用遞歸關(guān)系構(gòu)造模型用遞歸關(guān)系構(gòu)造模型復(fù)合利息。假設(shè)一個人在銀行的賬戶上存了復(fù)合利息。假設(shè)一個人在銀行的賬戶上存了10000美元，復(fù)合年利息是美元，復(fù)合年利息是11%。那么。那么30年后賬上將有多年后賬上將有多少錢？少錢？解：解：令令Pn表示表示n年后賬上的錢。因年后賬上的錢。因為為n年后的錢等于年后的錢等于n-1年后賬上的錢年后賬上的錢加上第加上第n年的利息，所以序列年的利息，所以序列Pn滿足遞歸關(guān)系滿足遞歸關(guān)系Pn=Pn-1+0.11Pn

12、-1=1.11Pn-1P0=10000P1=1.11 10000P2=1.11P1=1.112 10000Pn=1.11Pn-1=1.11n 10000 證明：證明：下面用數(shù)學(xué)歸納法驗證下面用數(shù)學(xué)歸納法驗證Pn=1.11n 10000的正確性的正確性歸納基礎(chǔ)：歸納基礎(chǔ)：n=0時顯然成立時顯然成立歸納推理：歸納推理：假設(shè)假設(shè)n=k時，時，Pk=1.11k 10000。那么由遞歸關(guān)系和歸納假設(shè)知那么由遞歸關(guān)系和歸納假設(shè)知P k+1=1.11Pk=1.11k+1 10000歸納完成，結(jié)論成立歸納完成，結(jié)論成立 12第第7講講 遞歸關(guān)系遞歸關(guān)系第12頁，共30頁。v用遞歸關(guān)系構(gòu)造模型用遞歸關(guān)系構(gòu)造模型

13、 例例3.15漢諾塔：游戲由漢諾塔：游戲由3根柱子和根柱子和64個大小不等的金盤組成。開始時，盤個大小不等的金盤組成。開始時，盤子按照大小次序放在第一根柱子上，大盤在下，小盤在上。游戲的規(guī)則子按照大小次序放在第一根柱子上，大盤在下，小盤在上。游戲的規(guī)則是，每次把一個盤子從一根柱子移動到另一根柱子上，并且不允許放在是，每次把一個盤子從一根柱子移動到另一根柱子上，并且不允許放在比它小的盤子上。游戲的目標是把所有盤子按照大小次序原樣搬到第二比它小的盤子上。游戲的目標是把所有盤子按照大小次序原樣搬到第二根柱子上，最大的盤子放在最下面。根柱子上，最大的盤子放在最下面。13第第7講講 遞歸關(guān)系遞歸關(guān)系第1

14、3頁，共30頁。v用遞歸關(guān)系構(gòu)造模型用遞歸關(guān)系構(gòu)造模型解：解：假設(shè)有假設(shè)有n個盤子，個盤子，H(n)表示解表示解n個盤子的漢諾個盤子的漢諾塔問題需要移動的次數(shù)。開始時，塔問題需要移動的次數(shù)。開始時，n個盤子在柱個盤子在柱1(1)H(n-1)次移動將次移動將柱柱1的的n-1個盤子移到柱個盤子移到柱3(2)一次移動把最大的盤子移到柱一次移動把最大的盤子移到柱2；(3)H(n-1)次移動把柱次移動把柱3的的n-1個盤子移到柱個盤子移到柱2。H(n)= 2H(n-1)+1，初始條件是，初始條件是H(1)=1。H(n)= 2H(n-1)+1=2(2H(n-2)+1)+1=22H(n-2)+2+1 = 2

15、3H(n-3)+22+2+1= = 2n-1H(n-(n-1)+2n-2+22+2+1 = 2n-1+2n-2+1 = 2n - 1證明：證明：用數(shù)學(xué)歸納法證明用數(shù)學(xué)歸納法證明H(n)= 2n -1歸納基礎(chǔ)：歸納基礎(chǔ)：n=1時，時，H(1)=21-1=1，成立，成立歸納推理：歸納推理：假設(shè)假設(shè)n=k(k1)時時,H(k) = 2k-1則則H(k+1)= 2H(k)+1 = 2(2k-1)+1 = 2k+1-1每秒移動一次，用每秒移動一次，用n=64代入，得代入，得H(64)= 264-1=18,446,744,073,709,551,615 秒秒=75000億年。億年。因此這個世界的壽命應(yīng)該比

16、它已有的因此這個世界的壽命應(yīng)該比它已有的壽命還長壽命還長 14第第7講講 遞歸關(guān)系遞歸關(guān)系第14頁，共30頁。v用遞歸關(guān)系構(gòu)造模型用遞歸關(guān)系構(gòu)造模型 兔子和兔子和費波那契（費波那契（Fibonacci）數(shù)）數(shù)。一對（一公一母）剛出生的小兔子放。一對（一公一母）剛出生的小兔子放到島上，每對兔子出生兩個月后開始繁殖后代，每對兔子每個月可以繁殖到島上，每對兔子出生兩個月后開始繁殖后代，每對兔子每個月可以繁殖一對新的小兔子。假定兔子不會死去，一對新的小兔子。假定兔子不會死去，n個月后島上共有多少對兔子？個月后島上共有多少對兔子？解：解：用用F(n)表示表示n個月后島上的兔子對數(shù)，規(guī)定個月后島上的兔子對

17、數(shù)，規(guī)定F(0)=0，且已知，且已知F(1)=1，F(xiàn)(2)=1。n個月后島上的兔子對數(shù)為前一個月島上的兔子個月后島上的兔子對數(shù)為前一個月島上的兔子對數(shù)對數(shù)F(n-1)加上第加上第n個月新出生的兔子對數(shù)，而這個月新出生的兔子對數(shù)，而這個數(shù)等于個數(shù)等于F(n-2)，因為每對兩個月大的兔子都生出，因為每對兩個月大的兔子都生出一對新兔子。一對新兔子。有遞歸關(guān)系有遞歸關(guān)系F(n)= F(n-1)+F(n-2) (n2)。加上初始條件得加上初始條件得該數(shù)列即稱為該數(shù)列即稱為費波納契數(shù)列費波納契數(shù)列)2() 1()(1) 1 (0)0(nFnFnFFF有多少個n位二進制串不包含兩個連續(xù)的0？ an = an

18、-1 + an-215第第7講講 遞歸關(guān)系遞歸關(guān)系第15頁，共30頁。v遞歸關(guān)系的求解遞歸關(guān)系的求解在前面的幾個問題中，除費波那契數(shù)之外的其它問在前面的幾個問題中，除費波那契數(shù)之外的其它問題都可以在求出初始值和遞歸關(guān)系式后題都可以在求出初始值和遞歸關(guān)系式后迭代求解迭代求解，找出數(shù)列的通項公式。方法是：找出數(shù)列的通項公式。方法是：首先利用遞歸關(guān)系式對關(guān)系式右邊的表達式進行迭代，首先利用遞歸關(guān)系式對關(guān)系式右邊的表達式進行迭代，并推測解的公式并推測解的公式然后用數(shù)學(xué)歸納法證明得到的公式然后用數(shù)學(xué)歸納法證明得到的公式費波那契數(shù)列不易迭代求解，但它有一種更系統(tǒng)的費波那契數(shù)列不易迭代求解，但它有一種更系統(tǒng)

19、的求解方法求解方法16第第7講講 遞歸關(guān)系遞歸關(guān)系第16頁，共30頁。v常系數(shù)線性齊次遞歸關(guān)系常系數(shù)線性齊次遞歸關(guān)系定義定義2（定義（定義3.7）：形如形如H(n)=c1H(n-1)+c2H(n-2)+ckH(n-k) 的遞歸關(guān)系式叫做的遞歸關(guān)系式叫做常系數(shù)常系數(shù)線性線性齊次齊次遞歸關(guān)系式遞歸關(guān)系式。其中。其中c1, c2, ck為常數(shù)，為常數(shù)， ck 0，kn常系數(shù)常系數(shù)系數(shù)系數(shù)c1, c2, ck為不依賴于為不依賴于n的常數(shù)的常數(shù)線性線性等式右邊為序列項的倍數(shù)之和等式右邊為序列項的倍數(shù)之和齊次齊次所出現(xiàn)的各項都是所出現(xiàn)的各項都是H(i)的倍數(shù)的倍數(shù)H(n)= nH(n-1)不是常系數(shù)的不是

20、常系數(shù)的 H(n)= H(n-1)+H(n-2)2不是線性的不是線性的H(n)= 2H(n-1)+1不是齊次的不是齊次的17第第7講講 遞歸關(guān)系遞歸關(guān)系第17頁，共30頁。v特征方程特征方程遞歸關(guān)系式遞歸關(guān)系式H(n)=c1H(n-1)+c2H(n-2)+ckH(n-k)求解的基本方法是尋找形如求解的基本方法是尋找形如an=rn的解，其中的解，其中r是常數(shù)是常數(shù)得到得到 rn - c1rn-1 - c2rn-2 - - ckrn-k = 0 rk - c1rk-1 - c2rk-2 - - ck = 0定義定義3 （P48） ：xk c1xk-1 c2xk-2 ck = 0稱為遞歸稱為遞歸關(guān)系

21、式關(guān)系式H(n)=c1H(n-1)+c2H(n-2)+ckH(n-k) 的的特征特征方程方程，其根為該遞歸關(guān)系式的其根為該遞歸關(guān)系式的特征根特征根an=rn是遞歸關(guān)系的解，當且僅當是遞歸關(guān)系的解，當且僅當r是其特征方程的根是其特征方程的根18第第7講講 遞歸關(guān)系遞歸關(guān)系第18頁，共30頁。v常系數(shù)線性齊次遞歸關(guān)系的求解常系數(shù)線性齊次遞歸關(guān)系的求解定理定理1：設(shè)設(shè)c1和和c2是實數(shù)，方程是實數(shù)，方程r2c1rc2=0有兩個不等的根有兩個不等的根r1和和r2，那，那么序列么序列an是遞歸關(guān)系是遞歸關(guān)系an = c1an-1 + c2an-2的解，當且僅當?shù)慕猓斍覂H當an = b1r1n + b2

22、 r2n ，n=0,1,2,，其中，其中b1 ，b2是常數(shù)是常數(shù)證明：（充分性）證明：（充分性）如果如果r1和和r2是特征方程的根，且是特征方程的根，且b1，b2是常數(shù)，那么序列是常數(shù)，那么序列an(an = b1r1n + b2r2n )是遞歸關(guān)系的解是遞歸關(guān)系的解。r1、r2是方程是方程r2 c1r c2 =0的根的根 r12= c1r1 + c2且且r22= c1r2 + c2c1an-1 + c2an-2 = c1(b1r1n-1 + b2r2n-1) + c2(b1r1n-2 + b2r2n-2) = b1r1n-2(c1r1 + c2) + b2r2n-2(c1r2 + c2) =

23、 b1r1n-2r12+ b2r2n-2r22 = b1r1n + b2r2n =an 即即an(an = b1r1n + b2r2n )是遞歸關(guān)系的解是遞歸關(guān)系的解 19第第7講講 遞歸關(guān)系遞歸關(guān)系第19頁，共30頁。v常系數(shù)線性齊次遞歸關(guān)系的求解常系數(shù)線性齊次遞歸關(guān)系的求解定理定理1：設(shè)設(shè)c1和和c2是實數(shù)，方程是實數(shù)，方程r2c1rc2=0有兩個不等的根有兩個不等的根r1和和r2，那么，那么序列序列an是遞歸關(guān)系是遞歸關(guān)系an = c1an-1 + c2an-2的解，當且僅當?shù)慕?，當且僅當an = b1r1n + b2 r2n ，n=0,1,2,，其中，其中b1 ，b2是常數(shù)是常數(shù)證明：

24、（必要性）證明：（必要性）如果如果r1和和r2是特征方程的根，且是特征方程的根，且an是滿足遞歸關(guān)系是滿足遞歸關(guān)系an=c1an-1+c2an-2的任一解。那么的任一解。那么an都具有都具有an=b1r1n+b2r2n的形式，的形式，n=0,1,，b1、b2是常數(shù)。數(shù)學(xué)歸納法證明。是常數(shù)。數(shù)學(xué)歸納法證明。(1)歸納基礎(chǔ)：歸納基礎(chǔ)：對對n=0、1，有：，有：a0 = G0 = b1+b2，a1 = G1 = b1r1+b2r2。得到得到(2)歸納推理歸納推理an =c1an-1 + c2an-2 = c1(b1r1n-1 + b2r2n-1) + c2(b1r1n-2 + b2r2n-2) =

25、b1r1n-2(c1r1 + c2) + b2r2n-2(c1r2 + c2) = b1r1n-2r12+ b2r2n-2r22 = b1r1n + b2r2n 212011rrrGGb211102rrGrGb1、r1r22、特征根是復(fù)數(shù)仍舊適用、特征根是復(fù)數(shù)仍舊適用20第第7講講 遞歸關(guān)系遞歸關(guān)系第20頁，共30頁。v常系數(shù)線性齊次遞歸關(guān)系的求解常系數(shù)線性齊次遞歸關(guān)系的求解求解費波那契數(shù)列的通項公式求解費波那契數(shù)列的通項公式解：費波那契數(shù)列的遞歸關(guān)系式為費波那契數(shù)列的遞歸關(guān)系式為F(n)= F(n-1)+F(n-2) (n2)，其特征方程，其特征方程x2-x-1=0有兩個不等的特征根有兩個不

26、等的特征根q1=，q2=。根據(jù)定理，該遞歸關(guān)系式有通解根據(jù)定理，該遞歸關(guān)系式有通解F(n)= c1 + c2 ，c1, c2為常數(shù)。為常數(shù)。F(0)=0，F(xiàn)(1)=1 解得解得c1= ，c2=費波那契數(shù)列的通項公式為費波那契數(shù)列的通項公式為F(n)= 251 251 n)251(n)251(125125102121cccc515151n)251(51n)251(21第第7講講 遞歸關(guān)系遞歸關(guān)系第21頁，共30頁。v常系數(shù)線性齊次遞歸關(guān)系的求解常系數(shù)線性齊次遞歸關(guān)系的求解 例例3.17 某人有某人有n(n1)元錢，他每天買一次物品，或者買一元錢的甲元錢，他每天買一次物品，或者買一元錢的甲物品，或

27、者買兩元錢的乙物品或丙物品。問此人有多少種方式花完物品，或者買兩元錢的乙物品或丙物品。問此人有多少種方式花完這這n元錢？元錢？解：解：設(shè)花完這設(shè)花完這n元錢有元錢有H(n)種方式?？煞秩N情況：（種方式?？煞秩N情況：（1）第一天買甲物品，）第一天買甲物品，共有共有H(n-1)種方式花完剩余的錢；（種方式花完剩余的錢；（2）第一天買乙物品，有）第一天買乙物品，有H(n-2)種方種方式花完剩余的錢；（式花完剩余的錢；（3）第一天買丙物品，有）第一天買丙物品，有H(n-2)種方式花完剩余的錢。種方式花完剩余的錢。根據(jù)加法原理，有根據(jù)加法原理，有H(n) = H(n-1) + 2 H(n-2) (n

28、3)該遞歸關(guān)系的特征方程為該遞歸關(guān)系的特征方程為x2-x-2=0，有兩個不等的特征根，有兩個不等的特征根q1=2，q2=1，所以其通解為所以其通解為H(n) = c12n + c2(1)n又又H(1)=1，H(2)=3 解得解得c1=2/3，c2=1/3H(n) = 2/32n + 1/3(1)n 22第第7講講 遞歸關(guān)系遞歸關(guān)系第22頁，共30頁。v常系數(shù)線性齊次遞歸關(guān)系的求解常系數(shù)線性齊次遞歸關(guān)系的求解例例3.18 求解遞歸關(guān)系式求解遞歸關(guān)系式H(0) = 1H(1) = 3H(n) = 4H(n-1) 4H(n-2) (n2)解：解：遞歸關(guān)系式的特征方程是遞歸關(guān)系式的特征方程是 x2-4

29、x+4=0 解之，得到兩個重根解之，得到兩個重根x1=2 , x2=2 ,于是遞歸關(guān)系式的通解于是遞歸關(guān)系式的通解 將初始值將初始值H(0) = 1，H(1) = 3代入得一個矛盾的方程組代入得一個矛盾的方程組求解失敗，顯然，必須改進上述方法求解失敗，顯然，必須改進上述方法 。nnnncccccnH22)(22)(21211c32 c 23第第7講講 遞歸關(guān)系遞歸關(guān)系第23頁，共30頁。v常系數(shù)線性齊次遞歸關(guān)系的求解常系數(shù)線性齊次遞歸關(guān)系的求解 定理2：設(shè)c1和c2是實數(shù)，方程r2c1rc2=0只有一個根r0，那么序列an是遞歸關(guān)系an = c1an-1 + c2an-2的解，當且僅當an =

30、 b1r0n + b2 nr0n ，n=0,1,2,，其中b1 ，b2是常數(shù) 求：具有初始條件a0=1和a1=6的遞推關(guān)系an=6an-1-9an-2解：解：r2 - 6r + 9 = 0唯一的根是唯一的根是r3 遞推關(guān)系的解是：遞推關(guān)系的解是：an=b13n+b2n3n，其中，其中b1和和b2是常數(shù)是常數(shù)使用初始條件得到使用初始條件得到a0=1=b1a1=6=b1*3+b2*1*3得到得到b1=1,b2=1得到：得到：an=3n+n3n24第第7講講 遞歸關(guān)系遞歸關(guān)系第24頁，共30頁。v常系數(shù)線性齊次遞歸關(guān)系的求解常系數(shù)線性齊次遞歸關(guān)系的求解例例3.19(例例3.18續(xù)續(xù)) 求解遞歸關(guān)系式

31、求解遞歸關(guān)系式H(0) = 1H(1) = 3H(n) = 4H(n-1) 4H(n-2) (n2)解：解：由于特征方程有兩個重根由于特征方程有兩個重根2，所以根據(jù)上面定理，其通解為，所以根據(jù)上面定理，其通解為 H(n) = (c1 + c2n) 2n 由由H(0) = 1，H(1) = 3代入得代入得 解得解得c1= 1，c2= 0.5 通解為通解為H(n) =(1 + n /2) 2n 3)(21211ccc25第第7講講 遞歸關(guān)系遞歸關(guān)系第25頁，共30頁。v常系數(shù)線性齊次遞歸關(guān)系的求解常系數(shù)線性齊次遞歸關(guān)系的求解定理定理3.18 設(shè)設(shè)q是一個非零的實數(shù)或復(fù)數(shù)，那么，是一個非零的實數(shù)或復(fù)

32、數(shù)，那么， 是遞歸關(guān)系式是遞歸關(guān)系式 的解當且僅當?shù)慕猱斍覂H當q是它的一個特征根。是它的一個特征根。 證證:若若 是遞歸關(guān)系式的解，那么是遞歸關(guān)系式的解，那么由于由于 因此，因此， ，也就是說，也就是說q是它的特征方程是它的特征方程 的一個的一個特征根。特征根。另一方面，上述推理過程是可逆的，故定理得證。另一方面，上述推理過程是可逆的，故定理得證。nqnH)(0)()2() 1()(21knHbnHbnHbnHk)0,(kbnknqnH)(02211knknnnqbqbqbq0)(2211kkknkknbqbqbqq 0q02211kkkkbqbqbq02211kkkkbxbxbx26第第7講講 遞歸關(guān)系遞歸關(guān)系第26頁，共30頁。v常系數(shù)線性齊次遞歸關(guān)系的求解常系數(shù)線性齊次遞歸關(guān)系的求解定理定理3.19