3.3.2 举例
(2)由于F(n)＝1＝1×1n且s＝1是(☆)的0重 根，所以得(＊)的一个特解形如 an＝n0×p×1n ＝p(p为待定系数) 代入(＊)得p＝－1 故得(＊)的一个特解an＝－1
3.3.2 举例
(3) (＊)的通解 an＝a×2n－1(a为任意常数)
代入a1＝1得a＝1 (4)求得递归的解an＝2n－1
an＝n1(p1n＋p0)1n(p1,p0为待定系数)
代入a1＝1，a2＝3得
p1 p0 1 2(2 p1 p0) 3
p0
1 2
p1
1 2
3.3.2 举例
故得(＊)的一个特解
an＝n1(
1 2
n＋
1 2
)1n ＝ 1
2
n2＋ 1
2
n
(3) (＊)的通解
an＝a＋
1 2
n2＋
1 2
n
3.3.2 举例
定理3.3.3若an＝x(n)和an＝y(n)分别是递推关系 an＝c1an-1＋c2an-2＋…＋ckan-k＋F1(n) an＝c1an-1＋c2an-2＋…＋ckan-k＋F2(n) 的解，其中c1,c2,…,ck(ck≠0)是实数常数，F1(n)与 F1(n)是只依赖于n且不恒为0的函数， 则an＝x(n)＋y(n)为递推关系 an＝c1an-1＋c2an-2＋…＋ckan-k＋F1(n)＋F2(n) 的解
3.3.2 举例
例3.3.1 解递归 an an1 n ()
a1
1
解(1)相伴齐次递推关系an＝an-1 (☆) (☆)的特征方程x－1＝0
(☆)的特征根 x＝1
(☆)的通解an＝a×1n＝a(a为任意常数)
3.3.2 举例
(2)由于F(n)＝n＝n×1n且s＝1是(☆)的1重
根，所以得(＊)的一个特解形如
3.3.1 非其次递推关系
定理3.3.2 设常系数线性非齐次递推关 an＝c1an-1＋c2an-2＋…＋ckan-k ＋F(n)
其中c1,c2,…,ck是实数常数，ck≠0； 且F(n)＝(btnt＋bt-1nt-1＋…＋b1n ＋b0)Sn 其中b1,b2,…,bt和S是实数常数。 当S是相伴的线性齐次递推关系的特征方程的 m(m≥0)重根时，存在一个下述形式的特解： an＝nm(ptnt＋pt-1nt-1＋…＋p1n＋p0)Sn 其中p1,p2,…,pt为待定系数。
3.3.2 举例
例3.3.3 解递归 an 3an1 3 2n 4n ()
a1 1
解(1)相伴齐次递推关系an＝3an-1 (☆) (☆)的特征方程x－3＝0 (☆)的特征根 x＝3 (☆)的通解an＝a×3n(a为任意常数)
3.3.2 举例
(2)分别求an＝3an-1＋3×2n (◇) an＝3an-1－4n (△)的一个特解
(◇)的一个特解形如b×2n (b为常数) 将其代入(◇)得b＝－6 故求得(◇)的一个特解an＝－6×2n
类似求得(△)的一个特解an＝2n＋3 故求得(＊)的一个特解an ＝－6×2n＋(＊)的通解 an＝a×3n－6×2n＋2n＋3(a为任意常数)
(4)代入a1＝8得a＝5。故求得递归的解 an＝5×3n－6×2n＋2n＋3
(a为任意常数)
代入a1＝1得a＝0
(4)求得递归的解an＝
1 2
n2＋
1 2
n
3.3.2 举例
例3.3.2 解Hanoi问题的递归，即
an 2an1 1 ()
a1
1
解(1)相伴齐次递推关系an＝2an-1 (☆)
(☆)的特征方程x－2＝0
(☆)的特征根 x＝2
(☆)的通解an＝a×2n(a为任意常数)
相伴的齐次递推关系 an＝c1an-1＋c2an-2＋…＋ckan-k (3.3.2)
3.3.1 非其次递推关系
定理3.3.1
若an＝x(n)为递推关系
(3.3.1)相伴的齐次递推关系(3.3.2)的通
解， an＝y(n)为递推关系(3.3.1)的一个 特解，则an＝x(n) ＋y(n)为递推关系 (3.3.1)的通解。
3.3常系数线性非其次递推关系 3.3.1 非其次递推关系 3.3.2 举例
3.3.1 非其次递推关系
常系数线性非其次递推关系 an＝c1an-1＋c2an-2＋…＋ckan-k ＋F(n) (3.3.1) 其中c1,c2,…,ck是实数常数，ck≠0； F(n)是只依赖于n且不恒为0的函数。