組合數(shù)學(xué)常系數(shù)線性非齊次遞推關(guān)系第1頁，課件共18頁，創(chuàng)作于2023年2月3.3.1非其次遞推關(guān)系常系數(shù)線性非其次遞推關(guān)系

an＝c1an-1＋c2an-2＋…＋ckan-k＋F(n)(3.3.1)

其中c1,c2,…,ck是實(shí)數(shù)常數(shù)，ck≠0；

F(n)是只依賴于n且不恒為0的函數(shù)。相伴的齊次遞推關(guān)系

an＝c1an-1＋c2an-2＋…＋ckan-k(3.3.2)第2頁，課件共18頁，創(chuàng)作于2023年2月3.3.1非其次遞推關(guān)系定理3.3.1

若an＝x(n)為遞推關(guān)系(3.3.1)相伴的齊次遞推關(guān)系(3.3.2)的通解，an＝y(tǒng)(n)為遞推關(guān)系(3.3.1)的一個特解，則an＝x(n)＋y(n)為遞推關(guān)系(3.3.1)的通解。第3頁，課件共18頁，創(chuàng)作于2023年2月3.3.1非其次遞推關(guān)系定理3.3.2

設(shè)常系數(shù)線性非齊次遞推關(guān)

an＝c1an-1＋c2an-2＋…＋ckan-k＋F(n)

其中c1,c2,…,ck是實(shí)數(shù)常數(shù)，ck≠0；且F(n)＝(btnt＋bt-1nt-1＋…＋b1n＋b0)Sn

其中b1,b2,…,bt和S是實(shí)數(shù)常數(shù)。當(dāng)S是相伴的線性齊次遞推關(guān)系的特征方程的m(m≥0)重根時，存在一個下述形式的特解：

an＝nm(ptnt＋pt-1nt-1＋…＋p1n＋p0)Sn

其中p1,p2,…,pt為待定系數(shù)。第4頁，課件共18頁，創(chuàng)作于2023年2月3.3.2舉例例3.3.1

解遞歸解(1)相伴齊次遞推關(guān)系an＝an-1(☆)(☆)的特征方程x－1＝0(☆)的特征根x＝1(☆)的通解an＝a×1n＝a(a為任意常數(shù))第5頁，課件共18頁，創(chuàng)作于2023年2月3.3.2舉例(2)由于F(n)＝n＝n×1n且s＝1是(☆)的1重根，所以得(＊)的一個特解形如an＝n1(p1n＋p0)1n(p1,p0為待定系數(shù))代入a1＝1，a2＝3得第6頁，課件共18頁，創(chuàng)作于2023年2月3.3.2舉例故得(＊)的一個特解

an＝n1(n＋)1n＝n2＋

n

(3)(＊)的通解

an＝a＋n2＋

n(a為任意常數(shù))

代入a1＝1得a＝0

(4)求得遞歸的解an＝n2＋

n第7頁，課件共18頁，創(chuàng)作于2023年2月3.3.2舉例例3.3.2解Hanoi問題的遞歸，即解(1)相伴齊次遞推關(guān)系an＝2an-1(☆)(☆)的特征方程x－2＝0(☆)的特征根x＝2(☆)的通解an＝a×2n(a為任意常數(shù))第8頁，課件共18頁，創(chuàng)作于2023年2月3.3.2舉例(2)由于F(n)＝1＝1×1n且s＝1是(☆)的0重根，所以得(＊)的一個特解形如an＝n0×p×1n＝p(p為待定系數(shù))代入(＊)得p＝－1故得(＊)的一個特解an＝－1第9頁，課件共18頁，創(chuàng)作于2023年2月3.3.2舉例

(3)(＊)的通解

an＝a×2n－1(a為任意常數(shù))

代入a1＝1得a＝1

(4)求得遞歸的解an＝2n－1第10頁，課件共18頁，創(chuàng)作于2023年2月3.3.2舉例定理3.3.3若an＝x(n)和an＝y(tǒng)(n)分別是遞推關(guān)系

an＝c1an-1＋c2an-2＋…＋ckan-k＋F1(n)an＝c1an-1＋c2an-2＋…＋ckan-k＋F2(n)

的解，其中c1,c2,…,ck(ck≠0)是實(shí)數(shù)常數(shù)，F(xiàn)1(n)與F1(n)是只依賴于n且不恒為0的函數(shù)，

則an＝x(n)＋y(n)為遞推關(guān)系

an＝c1an-1＋c2an-2＋…＋ckan-k＋F1(n)＋F2(n)

的解第11頁，課件共18頁，創(chuàng)作于2023年2月3.3.2舉例例3.3.3

解遞歸解(1)相伴齊次遞推關(guān)系an＝3an-1(☆)(☆)的特征方程x－3＝0(☆)的特征根x＝3(☆)的通解an＝a×3n(a為任意常數(shù))第12頁，課件共18頁，創(chuàng)作于2023年2月3.3.2舉例(2)分別求an＝3an-1＋3×2n(

)an＝3an-1－4n(△)的一個特解(

)的一個特解形如b×2n(b為常數(shù))

將其代入(

)得b＝－6

故求得(

)的一個特解an＝－6×2n類似求得(△)的一個特解an＝2n＋3故求得(＊)的一個特解an＝－6×2n＋2n＋3第13頁，課件共18頁，創(chuàng)作于2023年2月3.3.2舉例

(3)(＊)的通解

an＝a×3n－6×2n＋2n＋3(a為任意常數(shù))

(4)代入a1＝8得a＝5。故求得遞歸的解