2-3 线性常系数递推关系

nullnull2.3 线性常系数递推关系 线性常系数齐次递推关系 线性常系数非齐次递推关系null1. 线性常系数齐次递推关系确定一个数列{an}的最常用的方法是：(1) 给出一般项an的表达式;(2) 得到该数列的母函数;(3) 建立数列所满足的递推关系。一个r-阶递推关系定义为：有正整数r 以及一个 r+1元函数F，使得对所有nr, 有关系式这样若已知这个数列的前r项a0,a1,…,ar-1(称为初始条件)，则可以通过递推关系逐项确定整个数列。null定义：如果序列{an}满足如果b(n)=0，则称为齐次的，否则称为非齐次的。则(1)称为一个k阶线性常系数递推关系，(2)称为初始条件。null先考虑二阶线性常系数齐次递推关系，即令母函数为G(x)=a0+a1x+a2x2+…，则null因此有与分母相对应的方程 x2+bx+c=0 称为特征方程，它的根称为特征根。这样G(x)可以表示为：null(1) 如果r1≠r2，则下面要根据特征根来进行分类讨论。因此通项表达式为：其中常数A, B可以利用待定系数法确定，或者利用初始条件(A+B=a0, Ar1+Br2=a1)来确定。null(1)’ 如果r1≠r2，且是一对共轭复根，则可以假设这样就有：定义两个新的待定常数：则通项表达式为：其中k1, k2由初始条件决定。null(2) 如果r1=r2，则可以令r=r1=r2=-b/2，因此通项表达式为：其中常数C, D可以利用初始条件来确定。例如，若已知a0, a1，则null例1 求解递推关系：特征方程为因此通项表达式可以设为：解得特征根为代入初始条件有因此通项表达式为：null例2 求解递推关系：特征方程为因此通项表达式可以设为：解得特征根为代入初始条件有因此通项表达式为：null例3 Fibonacci数列：特征方程为因此通项表达式可以设为：解得特征根为代入初始条件有因此通项表达式为：null例4 求解递推关系：特征方程为因此通项表达式可以设为：解得特征根为代入初始条件有因此通项表达式为：null接下来讨论一般的k阶线性常系数齐次递推关系：类似的，令母函数为G(x)=a0+a1x+a2x2+…，则+)null整理得其中右端是次数不超过k-1次的多项式，设为P(x)。定义为特征方程，它在复数域内刚好有k个根，即其中k1+…+ki=k。这些根称为特征根。这样，等式左边的函数可以表示为：null即null(1) 如果所有特征根都互不相同，则下面同样要根据特征根来进行分类讨论。因此通项表达式为：其中常数A1, A2, … , Ak可以利用初始条件来确定。null(1)’ 如果有一对共轭复根(重数都为1)，重复以前的讨论，不妨假设这一对共轭复根是则an的通项表达式中对应于的项为：其中常数A1, A2和通项表达式中的其他常数一起由初始条件来决定。null(2) 如果有重根，不妨假设a1是m重根，则母函数中对应于a1的项可以表示为因此通项表达式中对应于a1的部分为：注意到C( j+n-1, n)=C( j+n-1, j-1)是n的j-1次多项式，因此这部分也可以表示为null例5 求下列n阶行列式的值dn：特征方程为根据行列式的性质有：null这是一个二重根，因此通项表达式可以设为：解得特征根为代入初始条件有因此n阶行列式的值为：null例6 计算Sn=1+2+…+n。显然有 Sn-Sn-1=n，但这不是一个齐次递推关系。注意到 Sn-1-Sn-2=n-1，两式相减有这是一个三阶线性常系数齐次递推关系。特征方程为解得特征根为这是一个三重根，因此可以设null代入初始条件有因此有：null例7 计算Sn=12+22+…+n2。显然有 Sn-Sn-1=n2， Sn-1-Sn-2=(n-1)2，两式相减有特征方程为解得特征根为这是一个四重根，因此可以设null代入初始条件有因此有：null代入初始条件有因此有：另外一种更快的方法：由于已经知道Sn是三次多项式，因此可以假设null例8 计算Sn=13+23+…+n3。显然有 Sn-Sn-1=n3，类似前面的讨论容易得到特征方程为解得特征根为这是一个五重根，因此Sn是一个四次多项式，所以可以设代入初始条件有null因此有：可以令n=5做验证：S5=S4+53=225，null例9 求解递推关系：特征方程为因此通项表达式可以设为：解得特征根为null代入初始条件有因此通项表达式为：null2. 线性常系数非齐次递推关系对于一个k阶线性常系数非齐次递推关系：与一般的线性问题类似，它的通解可以表示为特解与对应的齐次问题通解的和，即其中an*是非齐次递推关系的一个特解，而an’是对应的齐次递推关系的通解。null关于齐次递推关系的通解，我们已经讨论完全了。因此关键在于如何得到非齐次递推关系的一个特解。下面我们针对一些特殊的右端项来讨论如何得到特解。例10 求递推关系：的一个特解。假设有如下形式的特解代入原递推关系，并整理后可得null因此有因此可以得到一个特解解得null(1) 一般来说，当右端项b(n)是n的k次多项式时，特解形式也可以设为k次多项式，即其中系数Ai由代入非齐次递推关系后确定。假设有如下形式的特解代入原递推关系，并整理后易有但这是不可能的！null问题出在当1是原递推关系的特征根时，若把特解设为多项式，代入递推关系后，最高次会被消去。回到上例，因此1是一重特征根，因此特解设为代入原递推关系，并整理后可得(2) 当右端项b(n)是n的k次多项式时，若1是递推关系的t重特征根，则特解的次数要提高t次，即null例12 求递推关系：的一个特解。假设有如下形式的特解代入原递推关系有化简得42A=42×16，即A=16。因此可以得到一个特解null例13 求递推关系：的一个特解。注意到2是递推关系的一个特征根，因此2n是对应齐次递推关系的解，即若把特解设为A×2n，则代入递推关系后，左端为0，无法解出A。代入原递推关系有化简求得A=-2。因此可以得到一个特解因此可以设特解形式为：null(3) 当右端项b(n)是常数乘以sn的形式时，若s是递推关系的t重特征根，则特解形式可以设为其中系数A由代入非齐次递推关系后确定。注意这包含了s不是特征根的情形，即t=0.把上面三种情况综合在一起，我们有下面的结论：若右端项b(n)=f(n)sn，其中f(n)是n的k次多项式，s是递推关系的t(t=0,1,2,…)重特征根，则特解形式可以设为null例14 求递推关系：的通解。显然特征根为-5,2，-7不是特征根，因此特解可设为代入原递推关系解得注意到对应齐次递推关系的通解为A(-5)n+B2n，因此原递推关系的通解为其中A,B由初始条件确定。null例15 求递推关系：的通解。显然特征根为-5，2，2是1重根，因此特解可以设为代入原递推关系解得注意到对应齐次递推关系的通解为A(-5)n+B2n，因此原递推关系的通解为其中A,B由初始条件确定。null例16 求Sn=12+22+…+n2。显然Sn满足Sn-Sn-1=n2，这是一个非齐次递推关系。由于1是递归关系的1重特征根，因此在设特解时需要把右端非齐次项中的多项式次数提高一次，即设另一方面，对应齐次递推关系的通解为常数，因此Sn应该是一个三次多项式，即可设为常数A, B, C, D代入初始条件即可确定。同样的技巧可以用来计算Sn=13+23+…+n3等。null叠加原理：设右端项b(n)有如下形式：则非齐次递推关系的一个特解为其中ai是右端项为bi(n)时对应的特解。例17 求递推关系：的一个特解。根据叠加原理，问题变为求当右端项分别为42∙4n和2n时的特解，而这前面已经计算过了。因此特解为