##### 线性递推关系 - 线性递推关系 - **线性递推关系**是指[[序列]]每一项都可以通过前几项的[[线性组合]]来表示的[[递推关系]], 可能包含一个与序列项无关的常数项或者函数项作为非齐次项, 如果 $f(n) = 0$, 则称为齐次递推关系, 否则为非齐次递推关系. 可以使用特征方程 $a_n = r^n$ 或者[[生成函数]]求解 - $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k} + f(n)$ - $r^n = c_1 r^{n-1} + c_2 r^{n-2} + \cdots + c_kr^{n-k}$ >[!example]- 线性递推关系 > - 斐波那契数列 > - $F_n = F_{n-1} + F_{n-2}$, $F_0 = 0, F_1 = 1$ > - 写出特征方程 > - $x^n = x^{n-1} + x^{n-2} \Rightarrow x^2 = x + 1 \Rightarrow x^2 - x - 1 = 0$ > - 解特征方程 > - $\displaystyle x = \frac{1 \pm \sqrt{5}}{2} \Rightarrow \alpha = \frac{1 + \sqrt{5}}{2}, \beta = \frac{1 - \sqrt{5}}{2}$ > - 写出通解形式 > - 若根不重 $\alpha \neq \beta$, 则通解是 $a_n = A \alpha^n + B \beta^n$ > - 常数 $A, B$ 由初始条件确定 > - 代入初始条件求常数 > - 用 $F_0 = 0, F_1 = 1$ 解 > - $\begin{cases} A + B = 0 \\ A \alpha + B \beta = 1 \end{cases} \Rightarrow A = \frac{1}{\sqrt{5}}, B = -\frac{1}{\sqrt{5}}$ > - $\displaystyle F_n = \frac{1}{\sqrt{5}} \left( \alpha^n - \beta^n \right)$