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

3.2常系数线性齐次递推关系,3.2.1 递推关系(3.2.1)3.2.2 递推(3.2.1)的特征方程3.2.3 递推(3.2.1)的解3.2.4 递推(3.2.1)特征根互不同3.3.5 递推(3.2.1)特征根有重根,3.2.1 递推关系(3.2.1),常系数k阶线性齐次递推关系 anc1an-1c2an-2ckan-k()其中c1,c2,ck是实数常数，ck0,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.1)的特征方程 递推关系(3.2.1)的特征根,3.2.3 递推(3.2.1)的解,定理3.2.1 非零复数q是特征方程(3.2.2)的根，当且仅当anqn是递推关系(3.2.1)的解xkc1xk-1c2xk-2ck-1xck0()xq anqnanc1an-1c2an-2ckan-k()其中c1,c2,ck是实数常数，ck0,3.2.3 递推(3.2.1)的解,定理 若h1(n),h2(n),hk(n)是递推关系(3.2.1)的解，则它们的线性组合A1h1(n)A2h2(n)Akhk(n)也是递推关系(3.2.1)的解，其中A1,A2,Ak为常数。,3.2.4 递推(3.2.1)特征根互不同,定理 如果特征方程(3.2.2)有k个不同的根x1,x2,xk(可有共轭虚根)，则 anA1x1nA2x2nAkxkn 是递推关系(3.2.1)的通解，其中A1,A2,Ak为任意的常数。,3.2.4 递推(3.2.1)特征根互不同,例 解递归解 递推推关系fnfn-1fn-2()()的特征方程为x2x10()的特征根x1,x2()的通解,3.2.4 递推(3.2.1)特征根互不同,把f00,f11代入通解得因此所求递归的解为,3.2.4 递推(3.2.1)特征根互不同,定理中，若特征方程(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)特征根互不同,特征方程(3.2.2)有k个不同的根x1,x2,xk 递推关系(3.2.1)的通解 anA1x1nA2x2nAkxkn 共轭复根x1pei，x2pe-i递推关系(3.2.1)的通解anA1pncosn A2pnsinn A3x3n Akxkn,3.2.4 递推(3.2.1)特征根互不同,例 解递归解 递推推关系anan-1an-2()()的特征方程为x2x10()的特征根x1,x2()的通解,3.2.4 递推(3.2.1)特征根互不同,把a11,a20代入通解得因此所求递归的解为,3.3.5 递推(3.2.1)特征根有重根,定理 设q(q0)是递推关系(3.2.1)的特征方程(3.2.2)的m(m2)重根，则anntqn(t0,1,2,m1)都是递推关系(3.2.1)的解。,3.3.5 递推(3.2.1)特征根有重根,定理 设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)特征根有重根,例 解递归解 递推推关系an2an-1an-4()()的特征方程为x42x240()的特征根x1x2i,x3x4i()的通解,3.3.5 递推(3.2.1)特征根有重根,把a10,a21,a32,a43代入通解得因此所求递归的解为,