相关概念
线性递推关系：
一个常系数的k阶线性齐次递推关系是形如
an=c1an−1+c2an−2+...+ckan−k
的递推关系，其中c1,c2,...,ck是实数且ck≠0。该定义中的递推关系是线性的，因为它的右边是序列前项的倍数。该递推关系是齐次的，因为所出现的各项都是aj的倍数。该递推关系各项的系数都是常数而不是依赖于n的函数。该递推关系的阶为k ，因为an由序列前面的k项来表示。
特征方程：
求解常系数线性齐次递推关系的基本方法是寻找形如an=rn 的解。
an=rn是递推关系an=c1an−1+c2an−2+...+ckan−k的解当且仅当
rn=c1rn−1+c2rn−2+...+ckrn−k
方程两边同除rn−k并移项可得
rk−c1rk−1−c2rk−2−...−ck−1r−ck=0
上式称为该递推关系的特征方程。方程的解称为特征根。相关定理
1.求解常系数线性齐次递推关系：
【定理1】：设c1和c2是实数。假设r2−c1r−c2=0有两个不相等的根r1和r2，那么序列{an}是递推关系an=c1an−1+c2an−2的解，当且仅当an=α1rn1+α2rn2,n=0,1,2,...,其中α1和α2是常数。
【定理2】：设c1和c2是实数，c2≠0。假设r2−c1r−c2=0只有一个根r0。序列{an}是递推关系an=c1an−1+c2an−2的解，当且仅当an=α1rn0+α2nrn0,n=0,1,2,...，其中α1和α2是常数。
【定理3】：设c1,c2,...,ck是实数。假设特征方程
rk−c1rk−1−...−ck=0
有k个不相等的根r1,r2,...,rk 。那么序列{an}是递推关系
an=c1an−1+c2an−2+...+ckan−k
的解，当且仅当
an=α1rn1+α2rn2+...+αkrnk
n=0,1,2,....,α1,α2,...,αk是常数。
【定理4(一般性结果)】：设c1,c2,...,ck是实数，假设特征方程式
rk−c1rk−1−...−ck=0
有t个不相等的根r1,r2,...,rt，其重数分别为m1,m2,...,mt，满足mi≥1,i=1,2,...t,且m1+m2+...+mk=k。那么序列{an}是递推关系
an=c1an−1+c2an−2+...+ckan−k
的解，当且仅当
an=(α1,0+α1,1+...+α1,mi−1nmi−1+)rn1+(α2,0+α2,1+...+α2,mi−1nmi−1+)rn2+...+(αt,0+αt,1+...+αt,mt−1nmt−1+)rn1
n=0,1,2,...,其中αi,j是常数，1≤i≤t且0≤j≤mi−1
2.求解常系数线性非齐次递推关系
【定理5】：如果{a(p)n}是常系数非齐次线性递推关系
an=c1an−1+c2an−2+...+ckan−k+F(n)
的一个特解，那么每个解都是{a(p)n+a(h)n}的形式，其中{a(h)n}是相伴的齐次递推关系
an=c1an−1+c2an−2+...+ckan−k
的一个解。
可见，求解常系数非齐次递推关系的关键是找一个特解。然后每个解都是这个特解与相伴的齐次递推关系的一个解的和。
当F(n)是n的多项式与一个常数的n 次幂之积时，我们就能知道一个特解恰好是什么形式。
【定理6】：假设{an}满足线性非齐次递推关系
an=c1an−1+c2an−2+...+ckan−k+F(n)
其中c1,c2,...,ck是实数，且
F(n)=(btnt+bt−1nt−1+...+b1n+b0)sn
其中b0,b1,...,bt和s是实数。当s 不是相伴的线性齐次递推关系的特征方程的根时，存在一个下述形式的特解
(ptnt+pt−1nt−1+..+p1n+p0)sn
当s是特征方程的根且它的重数是m 时，存在一个下述形式的特解
nm(ptnt+pt−1nt−1+..+p1n+p0)sn
版权声明：本文为MyLinChi原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。