问题
求二阶常系数线性齐次递推数列$f_n=a\times f_{n-1} + b \times f_{n-2}$的通项公式
结论
先解出特征方程$x^2-a\times x - b = 0$，两根分别是$x_1,x_2$
如果$x_1 != x_2$ 则$f_n=A\times x_1^n+B\times x_2^n$
如果$x_1=x_2$ 则$f_n=(A+B\times n)\times x_1^n$
（$A,B$可以通过$f_0,f_1$求出）
应用
斐波那契数列$f_n=f_{n-1}+f_{n-2}$
求解$x^2-x-1=0$
$x_1=\frac{1+\sqrt{5}}{2},x_2=\frac{1-\sqrt{5}}{2}$
$f_0=A\times x_1^0+B\times x_2^0=0$
$f_1=A\times x_1^1+B\times x_2^1=1$
$A=\frac{\sqrt{5}}{5}, B=\frac{-\sqrt{5}}{5}$
所以$f_n=\frac{\sqrt{5}}{5} \times (\frac{1+\sqrt{5}}{2})^n+\frac{-\sqrt{5}}{5}\times (\frac{1+\sqrt{5}}{2})^n$
