组合数学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 (3.2.1) 其中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.2) (3.2.2)即为递推关系(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 (3.2.2) xq anqn anc1an-1c2an-2ckan-k (3.2.1) 其中c1,c2,ck是实数常数， ck0,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.2.4 递推(3.2.1)特征根互不同,定理3.2.3 如果特征方程(3.2.2)有k个不同的根x1,x2,xk (可有共轭虚根)，则 anA1x1nA2x2nAkxkn 是递推关系(3.2.1)的通解，其中A1,A2,Ak为任意的常数。,3.2.4 递推(3.2.1)特征根互不同,例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.3中，若特征方程(3.2.2)有共轭复根x1pei，x2pe-i 此时x1npnein，x2npne-in都是递推关系(3.2.1)的解。再由定理3.2.2知： 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)特征根互不同,例3.2.2 解递归 解 递推推关系anan-1an-2 () ()的特征方程为x2x10 ()的特征根x1 , x2 ()的通解,3.2.4 递推(3.2.1)特征根互不同,把a11, a20代入通解得 因此所求递归的解为,3.3.5 递推(3.2.1)特征根有重根,定理3.2.4 设q(q0)是递推关系(3.2.1)的特征方程(3.2.2)的m(m2)重根，则anntqn(t0,1,2,m1)都是递推关系(3.2.1)的解。,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为任意的常数。,3.3.5 递推(3.2.1)特征根有重根,例3.2.3 解递归 解 递推推关系an2an-1an-4 () ()的特征方程为x42x240 ()的特征根x1x2i , x3x4i ()的通解,3.3.5 递推(3.2.1)特征根有重根,把a10, a21,a32, a43代入通解得 因此所求递归的解为,