组合数学常系数线性齐次递推关系.pptx

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

1、3.2.2 递推(3.2.1)的特征方程把anxn(x0)代入递推关系(3.2.1)得 xnc1xn-1c2xn-2ckxn-k 用xn-k除上式两边得 xkc1xk-1c2xk-2ck-1xck xkc1xk-1c2xk-2ck-1xck0(3.2.2)(3.2.2)即为递推关系(3.2.1)的特征方程 递推关系(3.2.1)的特征根 第1页/共19页3.2.3 递推(3.2.1)的解定理3.2.1 非零复数q是特征方程(3.2.2)的根，当且仅当anqn是递推关系(3.2.1)的解xkc1xk-1c2xk-2ck-1xck0(3.2.2)xq anqnanc1an-1c2an-2ckan-

2、k (3.2.1)其中c1,c2,ck是实数常数，ck0第2页/共19页3.2.3 递推(3.2.1)的解定理3.2.2 若h1(n),h2(n),hk(n)是递推关系(3.2.1)的解，则它们的线性组合A1h1(n)A2h2(n)Akhk(n)也是递推关系(3.2.1)的解，其中A1,A2,Ak为常数。第3页/共19页3.2.4 递推(3.2.1)特征根互不同定理3.2.3 如果特征方程(3.2.2)有k个不同的根x1,x2,xk(可有共轭虚根)，则 anA1x1nA2x2nAkxkn 是递推关系(3.2.1)的通解，其中A1,A2,Ak为任意的常数。第4页/共19页3.2.4 递推(3.2

3、.1)特征根互不同例3.2.1 解递归解 递推推关系fnfn-1fn-2 ()()的特征方程为x2x10 ()的特征根x1 ,x2 ()的通解第5页/共19页3.2.4 递推(3.2.1)特征根互不同把f00,f11代入通解得因此所求递归的解为 第6页/共19页3.2.4 递推(3.2.1)特征根互不同定理3.2.3中，若特征方程(3.2.2)有共轭复根x1pei，x2pe-i 此时x1npnein，x2npne-in都是递推关系(3.2.1)的解。再由定理3.2.2知：x1n x2npncosn,x1n x2npnsinn 也都是递推关系(3.2.1)的解。第7页/共19页3.2.4 递推(

4、3.2.1)特征根互不同特征方程(3.2.2)有k个不同的根x1,x2,xk 递推关系(3.2.1)的通解 anA1x1nA2x2nAkxkn 共轭复根x1pei，x2pe-i递推关系(3.2.1)的通解anA1pncosn A2pnsinn A3x3n Akxkn第8页/共19页3.2.4 递推(3.2.1)特征根互不同例3.2.2 解递归解 递推推关系anan-1an-2 ()()的特征方程为x2x10 ()的特征根x1 ,x2 ()的通解第9页/共19页3.2.4 递推(3.2.1)特征根互不同把a11,a20代入通解得因此所求递归的解为 第10页/共19页3.3.5 递推(3.2.1)

5、特征根有重根定理3.2.4 设q(q0)是递推关系(3.2.1)的特征方程(3.2.2)的m(m2)重根，则anntqn(t0,1,2,m1)都是递推关系(3.2.1)的解。第11页/共19页3.3.5 递推(3.2.1)特征根有重根定理3.2.5 设x1,x2,xt-1,xt(tk)是特征方程(3.2.2)的t个不同根，且xt为m(mkt1)重根，则 anA1x1nA2x2nAt-1xt-1n n0Atxtnn1At+1xt+1n nm-1Akxkn 是递推关系(3.2.1)的通解，其中A1,A2,Ak为任意的常数。第12页/共19页3.3.5 递推(3.2.1)特征根有重根例3.2.3 解递归解 递推推关系an2an-1an-4 ()()的特征方程为x42x240 ()的特征根x1x2i,x3x4i ()的通解第13页/共19页3.3.5 递推(3.2.1)特征根有重根把a10,a21,a32,a43代入通解得因此所求递归的解为 第14页/共19页第15页/共19页第16页/共19页第17页/共19页第18页/共19页感谢您的观看！第19页/共19页