特征根法小结

特征方程

特征方程可以用于求解线性递推数列的通项公式。其方法是将数列假设为一个等比数列并求出特征根，再代入初始数列的值求出特征根的系数得到通项公式。

斐波那契数列

我们以一个广为人知的数列举例。考虑斐波那契数列：

$$F_0=0,\\ F_1=1,\\ F_n=F_{n-1}+F_{n-2}$$

设$F_n=\lambda^n$，则可以得到

$$\lambda^n=\lambda^{n-1}+\lambda^{n-2}$$

令$n=2$：

$$\lambda^2=\lambda+1$$

解方程得到

$$\lambda_1=\frac{1+\sqrt{5}}{2},\lambda_2=\frac{1-\sqrt{5}}{2}$$

于是数列的通项公式可以表示为（特征根法的结论）

$$F_n=p\lambda_1^n+q\lambda_2^n$$

把$n=0,n=1$代入上式得到

$$p\lambda_1+q\lambda_2=1\\ p+q=0$$ $$p=\frac{1}{\sqrt{5}},q=-\frac{1}{\sqrt{5}}$$

于是得到

$$F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$$