第二节 常系数线性齐次递推关系

§6.2常系数线性齐次递推关系《组合数学引论》

－Chapter6一、定义定义1(f(n)}为一数列,C1,C2,…,Ck为k个常数,且Ck≠0,则称递推关系：为k阶常系数线性齐次递推关系.若数列{bn}满足递推关系,即则称这个数列{bn}为递推关系的解．若{bn}还满足初始条件，则称{bn}为满足初始条件的特解，显然满足初始条件的特解是唯一的．(1)定义2方程称为递推关系(1)的特征方程，它的根称为递推关系的特征根．(1)由于Ck≠0，所以特征根为非零根．二、解的性质性质1．设q是非零复数,f(n)=qn为递推关系(1)的解的充要条件为q是递推关系(1)的一个特征根．证明设f(n)=qn为递推关系的解，即由于，所以

即q为递推关系的一个特征根．反之结论也成立．性质2．如果h1(n),h2(n)为递推关系(1)的两个解，则Ah1(n)+Bh2(n)也是递推关系(1)的解,其中A、B为任意常数．证明设Tn=Ah1(n)+Bh2(n),由于h1(n),h2(n)为递推关系的解，有，所以Ah1(n)+Bh2(n)为递推关系的解．这是解的线性叠加性质,可推广到m个解的情况.(1)三、递推关系的通解定义2设h1(n),h2(n),…,hk(n)为递推关系(1)的k个解,若对(1)的任一个解h(n),都可适当选择常数使得则称为递推关系(1)的通解,其中b1,b2,…,bk为任意常数．定理4.2.1若为递推关系(1)的k个互不相等的特征根,则为递推关系(1)的通解,其中为任意常数．证明显然为递推关系(1)的解.(1)设h(n)是递推关系(1)的任一个解,它由k个初值h(0)=a0,h(1)=a1,……,h(k-1)=ak-1唯一确定.因为方程组的系数行列式(Vandermonde行列式)不为零,所以方程组有唯一解即有结论成立.下面研究当特征根有重根时，递推关系的通解．引理1.若q为k阶常系数线性齐次递推关系(1)的二重特征根，则为递推关系的解．证明令因为q为P(x)的二重根，所以q也为Pn(x)的二重根，从而q为的一重根，也为的一重根．又由于即为递推关系(1)的解．由引理1易证得下面的引理2.(1)引理2.若q为k阶常系数线性齐次递推关系（1）的m重特征根则为递推关系的解．定理2是递推关系(1)的全部不同特征根，其重数分别为,则递推关系的通解为其中．例1求解递推关系解它的特征方程为：特征根为:所以递推关系的通解为代入初值得方程组解方程组得所以递推关系的解为：例2求解递推关系解递推关系的特征方程为：特征根为:所以递推关系的通解为代入初值得方程组：解方程组得：,所以递推关系的解为：例3核反应堆中有和两种粒子，每秒钟内一个粒子可反应产生三个粒子，而一个粒子又可反应产生一个粒子和两个粒子.若在时刻t=0时反应堆中只有一个粒子,问t=100秒时反应堆将有多少个粒子?多少个粒子?共有多少个粒子?解设在t时刻的粒子数为f(t),粒子数为g(t)，依题意的下面递推关系它的特征方程为：特征根为:所以递推关系的通解为代人初值有解方程组，得所以递推关系的解为从而有因此，例4求解递推关系解递推关系的特征方程为：特征根为:所以递推关系的通解为代入初值得方程组：