組合數(shù)學(xué) 3.3常系數(shù)線性非齊次遞推關(guān)系

1、3.3常系數(shù)線性非其次遞推關(guān)系 3.3.1 非其次遞推關(guān)系 3.3.2 舉例13.3.1 非其次遞推關(guān)系常系數(shù)線性非其次遞推關(guān)系 anc1an-1c2an-2ckan-k F(n) (3.3.1) 其中c1,c2,ck是實(shí)數(shù)常數(shù)，ck0； F(n)是只依賴于n且不恒為0的函數(shù)。相伴的齊次遞推關(guān)系 anc1an-1c2an-2ckan-k (3.3.2)23.3.1 非其次遞推關(guān)系定理3.3.1 若anx(n)為遞推關(guān)系(3.3.1)相伴的齊次遞推關(guān)系(3.3.2)的通解， any(n)為遞推關(guān)系(3.3.1)的一個特解，則anx(n) y(n)為遞推關(guān)系(3.3.1)的通解。 33.3.1 非

2、其次遞推關(guān)系定理3.3.2 設(shè)常系數(shù)線性非齊次遞推關(guān) anc1an-1c2an-2ckan-k F(n) 其中c1,c2,ck是實(shí)數(shù)常數(shù)，ck0； 且F(n)(btntbt-1nt-1b1n b0)Sn 其中b1,b2,bt和S是實(shí)數(shù)常數(shù)。 當(dāng)S是相伴的線性齊次遞推關(guān)系的特征方程的m(m0)重根時，存在一個下述形式的特解： annm(ptntpt-1nt-1p1np0)Sn 其中p1,p2,pt為待定系數(shù)。 43.3.2 舉例例3.3.1 解遞歸解(1)相伴齊次遞推關(guān)系anan-1 () ()的特征方程x10 ()的特征根 x1 ()的通解ana1na(a為任意常數(shù))53.3.2 舉例(2)由

3、于F(n)nn1n且s1是()的1重 根，所以得()的一個特解形如 ann1(p1np0)1n(p1,p0為待定系數(shù)) 代入a11，a23得63.3.2 舉例 故得()的一個特解 ann1( n )1n n2 n (3) ()的通解 ana n2 n (a為任意常數(shù)) 代入a11得a0 (4)求得遞歸的解an n2 n 73.3.2 舉例例3.3.2 解Hanoi問題的遞歸，即解(1)相伴齊次遞推關(guān)系an2an-1 () ()的特征方程x20 ()的特征根 x2 ()的通解ana2n(a為任意常數(shù))83.3.2 舉例(2)由于F(n)111n且s1是()的0重 根，所以得()的一個特解形如 a

4、nn0p1n p(p為待定系數(shù)) 代入()得p1 故得()的一個特解an193.3.2 舉例 (3) ()的通解 ana2n1(a為任意常數(shù)) 代入a11得a1 (4)求得遞歸的解an2n1103.3.2 舉例定理3.3.3若anx(n)和any(n)分別是遞推關(guān)系 anc1an-1c2an-2ckan-kF1(n) anc1an-1c2an-2ckan-kF2(n) 的解，其中c1,c2,ck(ck0)是實(shí)數(shù)常數(shù)，F(xiàn)1(n)與F1(n)是只依賴于n且不恒為0的函數(shù)， 則anx(n)y(n)為遞推關(guān)系 anc1an-1c2an-2ckan-kF1(n)F2(n) 的解113.3.2 舉例例3.3.3 解遞歸解(1)相伴齊次遞推關(guān)系an3an-1 () ()的特征方程x30 ()的特征根 x3 ()的通解ana3n(a為任意常數(shù))123.3.2 舉例(2)分別求an3an-132n () an3an-14n ()的一個特解()的一個特解形如b2n (b為常數(shù)) 將其代入()得b6 故求得()的一個特解an62n類似求得()的一個特解an2n3故求得()的一個特解an 62n2n31