常係數線性遞推數列

常係數線性遞推數列，由初始值和下述形式的方程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