组合数学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阶线性齐次递推关系an c1an 1 c2an 2 ckan k 3 2 1 其中c1 c2 ck是实数常数 ck 0 3 2 2递推 3 2 1 的特征方程 把an xn x 0 代入递推关系 3 2 1 得xn c1xn 1 c2xn 2 ckxn k用xn k除上式两边得xk c1xk 1 c2xk 2 ck 1x ckxk c1xk 1 c2xk 2 ck 1x ck 0 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 的根 当且仅当an qn是递推关系 3 2 1 的解xk c1xk 1 c2xk 2 ck 1x ck 0 3 2 2 x qan qnan c1an 1 c2an 2 ckan k 3 2 1 其中c1 c2 ck是实数常数 ck 0 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 可有共轭虚根 则an A1x1n A2x2n Akxkn是递推关系 3 2 1 的通解 其中A1 A2 Ak为任意的常数 3 2 4递推 3 2 1 特征根互不同 例3 2 1解递归解递推推关系fn fn 1 fn 2 的特征方程为x2 x 1 0 的特征根x1 x2 的通解 3 2 4递推 3 2 1 特征根互不同 把f0 0 f1 1代入通解得因此所求递归的解为 3 2 4递推 3 2 1 特征根互不同 定理3 2 3中 若特征方程 3 2 2 有共轭复根x1 pei x2 pe i 此时x1n pnein x2n pne in 都是递推关系 3 2 1 的解 再由定理3 2 2知 x1n x2n pncosn x1n x2n pnsinn 也都是递推关系 3 2 1 的解 3 2 4递推 3 2 1 特征根互不同 特征方程 3 2 2 有k个不同的根x1 x2 xk递推关系 3 2 1 的通解an A1x1n A2x2n Akxkn共轭复根x1 pei x2 pe i 递推关系 3 2 1 的通解an A1pncosn A2pnsinn A3x3n Akxkn 3 2 4递推 3 2 1 特征根互不同 例3 2 2解递归解递推推关系an an 1 an 2 的特征方程为x2 x 1 0 的特征根x1 x2 的通解 3 2 4递推 3 2 1 特征根互不同 把a1 1 a2 0代入通解得因此所求递归的解为 3 3 5递推 3 2 1 特征根有重根 定理3 2 4设q q 0 是递推关系 3 2 1 的特征方程 3 2 2 的m m 2 重根 则an ntqn t 0 1 2 m 1 都是递推关系 3 2 1 的解 3 3 5递推 3 2 1 特征根有重根 定理3 2 5设x1 x2 xt 1 xt t k 是特征方程 3 2 2 的t个不同根 且xt为m m k t 1 重根 则an A1x1n A2x2n At 1xt 1n n0Atxtn n1At 1xt 1n nm 1Akxkn是递推关系 3 2 1 的通解 其中A1 A2 Ak为任意的常数 3 3 5递推 3 2 1 特征根有重根 例3 2 3解递归解递推推关系an 2an 1 an 4 的特征方程为x4 2