递归数列特征方程的推导过程

a(n+2)=p*a(n+1)+q*an

其特征方程为x^2-p*x-q=0

i.若其有两个不相等的根（称作特征根）α、β

则an=A*α^n+B*β^n

其中常数A、B的值由初始值a1、a2的值确定.

ii.若其有两个相等的根α

则an=(A*n+B)*α^n

其中常数A、B的值由初始值a1、a2的值确定.

最终可得：

当{an}有两个不等的特征根为根α,β时

由

a(n+2)-α*a(n+1)=β^(n-1)*(a2-α*a1)

a(n+2)-β*a(n+1)=α^(n-1)*(a2-β*a1)

得

an=((a2-β*a1)/(α-β))*α^(n-1)-((a2-β*a1)/(α-β))*β^(n-1)

或由

A*α+B*β=a1

A*α^2+B*β^2=a2

可得

A=(a2-β*a1)/(α^2-α*β)

B=(a2-β*a1)/(β^2-α*β)

得

an=((a2-β*a1)/(α-β))*α^(n-1)+((a2-β*a1)/(β-α))*β^(n-1)

当特征根为重根α时

由

an-α*a(n-1)=α^(n-2)*(a2-α*a1)

α*a(n-1)-α^2*a(n-2)=α^(n-2)*(a2-α*a1)

…

α^(n-2)*a2-α^(n-1)*a1=α^(n-2)*(a2-α*a1)

an-α^(n-1)*a1=(n-1)*α^(n-2)*(a2-α*a1)

得

an=((a2-a1*α)*n+2*a1*α-a2)*α^(n-2)

或由

(A+B)*α=a1

(2*A+B)*α^2=a2

可得

A=(a2-a1*α)/(α^2)

A=(2*a1*α-a2)/(α^2)

得

((a2-a1*α)*n+2*a1*α-a2)*α^(n-2)

由于

α+β=A

α*β=-B

由韦达定理，可构造一元二次方程

x^2-p*x-q=0

此即为二阶常系数齐次线性递推数列

a(n+2)=p*a(n+1)+q*an

的特徵方程

特殊的，当二阶常系数齐次线性递推数列

a(n+2)=p*a(n+1)+q*an

的特徵根为重根α=1时

即p=2，q=-1

a(n+2)=2*a(n+1)-an

此时，二阶常系数齐次线性递推数列

a(n+2)=2*a(n+1)-an

为等差数列