二阶齐次线性递推式：#

考虑一个序列(a_n=Aa_{n-1}+Ba_{n-2})的通项公式。

设(x,y)则有：

(a_n-xa_{n-1}=y(a_{n-1}-xa_{n-2}))

意义就是构造一个等比数列。

继续推：

(a_n=(x+y)a_{n-1}-xya_{n-2})

等量代换：

(A=x+y,B=-xy.)

这个序列的特征方程定义为：(x^2=Ax+B)

解出来得到：(x_1=frac{A+sqrt{A^2+4B}}{2},x_2=frac{A-sqrt{A^2+4B}}{2})

又因为(A=x+y)得到(y_1=frac{A-sqrt{A^2+4B}}{2},y_2=frac{A+sqrt{A^2+4B}}{2}.)

根据前面式子(a_n-xa_{n-1})是公比为(y)的等比数列。

设另一序列(S)表示这个等比数列。

(S_1=a_1-xa_0,S_i=a_i-xa_{i-1},S_i=S_1q^{i-1})

得到(a_i-xa_{i-1}=(a_1-xa_0)q^{i-1})

对应两根(x,y)带入得到方程组：

(a_i-x_1a_{i-1}=(a_1-x_1a_0)y_1^{i-1})

(a_i-x_2a_{i-1}=(a_1-x_2a_0)y_2^{i-1})

联立一下方程：上式乘以(x_2),下式乘(x_1)得到

(x_2a_i-x_1x_2a_{i-1}=x_2(a_1-x_1a_0)y_1^{i-1})

(x_1a_i-x_1x_2a_{i-1}=x_1(a_1-x_2a_0)y_2^{i-1})

相减：

((x_2-x_1)a_i=x_2(a_1-x_1a_0)y_1^{i-1}-x_1(a_1-x_2a_0)y_2^{i-1})

(a_i=frac{x_2(a_1-x_1a_0)y_1^{i-1}-x_1(a_1-x_2a_0)y_2^{i-1}}{x_2-x_1})

对比一下(x,y)的关系，可以得到：

(y_1=x_2,y_2=x_1)

于是，可以将式子转化为：

[a_i=frac{(a_1-x_1a_0)x_2^i-(a_1-x_2a_0)x_1^i}{x_2-x_1} ]

观察到，这个式子就是该序列的通项公式。

于是我们可以大力解出特征方程的解，带入如上式子得到通解。

线性分式递推式#

对于形如(a_{n+1}=frac{a·a_n+b}{c·a_n+d})的递推式：

令两边同时(+t)得：

(a_{n+1}+t=frac{a·a_n+b}{c·a_n+d}+t=(a+ct)frac{a_n+frac{b+dt}{a+ct}}{c·a_n+d})

带入一下发现是对的。

令(t=frac{b+dt}{a+ct},)解分式方程化简，两边同乘分母得到：

(ct^2+(a-d)t-b=0),解出(t_1,t_2)两个根带入上式得方程组：

(a_{n+1}+t_1=(a+ct_1)frac{a_n+t_1}{c·a_n+d})

(a_{n+1}+t_2=(a+ct_2)frac{a_n+t_2}{c·a_n+d})

两式子相除得到：

[frac{a_{n+1}+t_1}{a_{n+1}+t_2}=frac{a_n+t_1}{a_n+t_2}·frac{a+ct_1}{a+ct_2} ]

所以，(frac{a_{n+1}+t_1}{a_{n+1}+t_2})是公比为(frac{a+ct_1}{a+ct_2})的等比数列。

也就是说，这个序列形如(a_n=qa_{n-1}).

那么等比数列通项公式(a_n=a_1*q^{n-1}).同理得到：

[frac{a_{n+1}+t_1}{a_{n+1}+t_2}=frac{a_1+t_1}{a_1+t_2}(frac{a+ct_1}{a+ct_2})^{n} ]

也就是说，我们把通项公式写成了(frac{x+y_1}{x+y_2}=C)的形式。

解一下：

(x+y_1=C(x+y_2))

(x+y_1=Cx+Cy_2)

(x-Cx=Cy_2-y_1)

((1-C)x=Cy_2-y_1)

(x=frac{Cy_2-y_1}{1-C}).

那么通项公式可以写成：

[a_{n+1}=frac{(frac{a+ct_1}{a+ct_2})^{n}t_2-t_1}{1-(frac{a+ct_1}{a+ct_2})^{n}} ]

题目得解。

对于这类递推序列，它的特征方程是：(x=frac{ax+b}{cx+d},)即(cx^2+(a-d)x-b=0).