由初始值和下述形式的方程

A(n+k)=F(A(n+k-1),....A(n))------------------------------------------1

确定的数列{A(n)}称为k阶递推数列

特别的,当1的形式为

A(n+k)=C1A(n+k-1)+C2A(n+k-2)+......+CkA(n)+F(n)-----------------------2

时,数列{A(n)}称为k阶常系数线性递推数列.这里C1,C2.....,Ck为常数,且Ck不为零.若函数F(x)=0,

则称由2确定的数列{A(n)}为k阶常系数线性递推数列

等差数列满足递推式An+2=2An+1-An;等比数列满足An+1=qAn(其中q为非零常数).它们是最简单的递推数列

对于k阶常系数线性递推数列，我们称多项式x^k=C1*x^{k-1}+C2*x^{k-2}+...+Ck为其特征多项式。

而如果其特征多项式有k个不同的复数根x1,x2,...,xk,那这个数列有通项公式

A(n)=d1*x1^n+d2*x2^n+...+dk*xk^n

其中d1,d2,...,dk为待定系数。

但是如果特征多项式存在重根，比如x1=x2=x3,我们需要将对应项d1*x1^n+d2*x2^n+d3*x3^n改为(d1+d2*n+d3*n^2)x1^n