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

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

1、3.2常系数线性齐次递推关系 n3.2.1 递推关系(3.2.1)n3.2.2 递推(3.2.1)的特征方程n3.2.3 递推(3.2.1)的解n3.2.4 递推(3.2.1)特征根互不同n3.3.5 递推(3.2.1)特征根有重根3.2.1 递推关系(3.2.1)n常系数常系数k阶阶线性线性齐次齐次递推关系递推关系 anc1an-1c2an-2ckan-k ()其中c1,c2,ck是实数常数，ck03.2.2 递推(3.2.1)的特征方程n把anxn(x0)代入递推关系(3.2.1)得 xnc1xn-1c2xn-2ckxn-k 用xn-k除上式两边得 xkc1xk-1c2xk-2ck-1xc

2、k xkc1xk-1c2xk-2ck-1xck0()()即为递推关系(3.2.1)的特征方程特征方程 递推关系(3.2.1)的特征根特征根 3.2.3 递推(3.2.1)的解n定理3.2.1 非零复数q是特征方程(3.2.2)的根，当且仅当anqn是递推关系(3.2.1)的解nxkc1xk-1c2xk-2ck-1xck0()xq anqnnanc1an-1c2an-2ckan-k ()其中c1,c2,ck是实数常数，ck03.2.3 递推(3.2.1)的解n定理 若h1(n),h2(n),hk(n)是递推关系(3.2.1)的解，则它们的线性组合A1h1(n)A2h2(n)Akhk(n)也是递推

3、关系(3.2.1)的解，其中A1,A2,Ak为常数。3.2.4 递推(3.2.1)特征根互不同n定理 如果特征方程(3.2.2)有k个不同的根x1,x2,xk(可有共轭虚根)，则 anA1x1nA2x2nAkxkn 是递推关系(3.2.1)的通解，其中A1,A2,Ak为任意的常数。3.2.4 递推(3.2.1)特征根互不同n例 解递归n解解 递推推关系fnfn-1fn-2 ()()的特征方程为x2x10 ()的特征根x1 ,x2 ()的通解3.2.4 递推(3.2.1)特征根互不同n把f00,f11代入通解得n因此所求递归的解为 3.2.4 递推(3.2.1)特征根互不同n定理中，若特征方程(

4、3.2.2)有共轭复根x1pei，x2pe-i 此时x1npnein，x2npne-in都是递推关系(3.2.1)的解。再由定理知：x1n x2npncosn,x1n x2npnsinn 也都是递推关系(3.2.1)的解。3.2.4 递推(3.2.1)特征根互不同n特征方程(3.2.2)有k个不同的根x1,x2,xk n递推关系(3.2.1)的通解 anA1x1nA2x2nAkxkn 共轭复根x1pei，x2pe-in递推关系(3.2.1)的通解anA1pncosn A2pnsinn A3x3n Akxkn3.2.4 递推(3.2.1)特征根互不同n例 解递归n解解 递推推关系anan-1an

5、-2 ()()的特征方程为x2x10 ()的特征根x1 ,x2 ()的通解3.2.4 递推(3.2.1)特征根互不同n把a11,a20代入通解得n因此所求递归的解为 3.3.5 递推(3.2.1)特征根有重根n定理 设q(q0)是递推关系(3.2.1)的特征方程(3.2.2)的m(m2)重根，则anntqn(t0,1,2,m1)都是递推关系(3.2.1)的解。3.3.5 递推(3.2.1)特征根有重根n定理 设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为任意的常数。3.3.5 递推(3.2.1)特征根有重根n例 解递归n解解 递推推关系an2an-1an-4 ()()的特征方程为x42x240 ()的特征根x1x2i,x3x4i ()的通解3.3.5 递推(3.2.1)特征根有重根n把a10,a21,a32,a43代入通解得n因此所求递归的解为