资源描述：
《组合数学 3.2常系数线性齐次递推关系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、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≠03.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、-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≠03.2.3递推(3.2.1)的解定理3.2.2若h1(n)
3、,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－
4、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
5、.2.1)的通解an＝A1x1n＋A2x2n＋…＋Akxkn共轭复根x1＝peiө，x2＝pe-iө递推关系(3.2.1)的通解an＝A1pncosnө＋A2pnsinnө＋A3x3n＋…＋Akxkn3.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
6、.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(＊
7、)(＊)的特征方程为x4＋2x2＋4＝0(＊)的特征根x1＝x2＝i,x3＝x4＝－i(＊)的通解3.3.5递推(3.2.1)特征根有重根把a1＝0,a2＝1,a3＝2,a4＝3代入通解得因此所求递归的解为
