组合数学 常系数线性非齐次递推关系幻灯片.ppt

《组合数学 常系数线性非齐次递推关系幻灯片.ppt》由会员分享，可在线阅读，更多相关《组合数学 常系数线性非齐次递推关系幻灯片.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、组合数学 常系数线性非齐次递推关系第1页，共18页，编辑于2022年，星期一3.3.1 非其次递推关系n常系数线性非其次递推关系常系数线性非其次递推关系 anc1an-1c2an-2ckan-k F(n)(3.3.1)其中c1,c2,ck是实数常数，ck0；F(n)是只依赖于n且不恒为0的函数。n相伴的齐次递推关系相伴的齐次递推关系 anc1an-1c2an-2ckan-k (3.3.2)第2页，共18页，编辑于2022年，星期一3.3.1 非其次递推关系n定理3.3.1 若anx(n)为递推关系(3.3.1)相伴的齐次递推关系(3.3.2)的通解，any(n)为递推关系(3.3.1)的一个特

2、解，则anx(n)y(n)为递推关系(3.3.1)的通解。第3页，共18页，编辑于2022年，星期一3.3.1 非其次递推关系n定理3.3.2 设常系数线性非齐次递推关 anc1an-1c2an-2ckan-k F(n)其中c1,c2,ck是实数常数，ck0；且F(n)(btntbt-1nt-1b1n b0)Sn 其中b1,b2,bt和S是实数常数。当S是相伴的线性齐次递推关系的特征方程的m(m0)重根时，存在一个下述形式的特解：annm(ptntpt-1nt-1p1np0)Sn 其中p1,p2,pt为待定系数。第4页，共18页，编辑于2022年，星期一3.3.2 举例n例3.3.1 解递归n

3、解(1)相伴齐次递推关系anan-1 ()()的特征方程x10 ()的特征根 x1 ()的通解ana1na(a为任意常数)第5页，共18页，编辑于2022年，星期一3.3.2 举例n(2)由于F(n)nn1n且s1是()的1重 根，所以得()的一个特解形如 ann1(p1np0)1n(p1,p0为待定系数)代入a11，a23得第6页，共18页，编辑于2022年，星期一3.3.2 举例 故得()的一个特解 ann1(n )1n n2 n (3)()的通解 ana n2 n(a为任意常数)代入a11得a0 (4)求得递归的解an n2 n 第7页，共18页，编辑于2022年，星期一3.3.2 举例

4、n例3.3.2 解Hanoi问题的递归，即n解(1)相伴齐次递推关系an2an-1 ()()的特征方程x20 ()的特征根 x2 ()的通解ana2n(a为任意常数)第8页，共18页，编辑于2022年，星期一3.3.2 举例n(2)由于F(n)111n且s1是()的0重 根，所以得()的一个特解形如 ann0p1n p(p为待定系数)代入()得p1 故得()的一个特解an1第9页，共18页，编辑于2022年，星期一3.3.2 举例 (3)()的通解 ana2n1(a为任意常数)代入a11得a1 (4)求得递归的解an2n1第10页，共18页，编辑于2022年，星期一3.3.2 举例n定理3.3

5、.3若anx(n)和any(n)分别是递推关系 anc1an-1c2an-2ckan-kF1(n)anc1an-1c2an-2ckan-kF2(n)的解，其中c1,c2,ck(ck0)是实数常数，F1(n)与F1(n)是只依赖于n且不恒为0的函数，则anx(n)y(n)为递推关系 anc1an-1c2an-2ckan-kF1(n)F2(n)的解第11页，共18页，编辑于2022年，星期一3.3.2 举例n例3.3.3 解递归n解(1)相伴齐次递推关系an3an-1 ()()的特征方程x30 ()的特征根 x3 ()的通解ana3n(a为任意常数)第12页，共18页，编辑于2022年，星期一3.

6、3.2 举例n(2)分别求an3an-132n ()an3an-14n ()的一个特解n()的一个特解形如b2n(b为常数)将其代入()得b6 故求得()的一个特解an62nn类似求得()的一个特解an2n3n故求得()的一个特解an 62n2n3第13页，共18页，编辑于2022年，星期一3.3.2 举例 (3)()的通解 ana3n62n2n3(a为任意常数)(4)代入a18得a5。故求得递归的解 an53n62n2n3第14页，共18页，编辑于2022年，星期一第15页，共18页，编辑于2022年，星期一第16页，共18页，编辑于2022年，星期一第17页，共18页，编辑于2022年，星期一第18页，共18页，编辑于2022年，星期一