设 $\alpha$ 和 $\beta$ 为代数方程的两个根

$$\lambda^2 = a\lambda + b$$

于是 $\alpha^{n+2} = a\alpha^{n+1} + b\alpha^n$ 和 $\beta^{n+2} = a\beta^{n+1} + b\beta^n$ ，这意味着 $y_n = \alpha^n$ 和 $y_n = \beta^n$ 是 (7.12) 的特解。由于 $(\lambda - \alpha)(\lambda - \beta) = 0$ 意味着 $\lambda^2 = (\alpha + \beta)\lambda - \alpha\beta$ 我们可以将 (7.12) 改写为

$$x_{n+2} = (\alpha + \beta)x_{n+1} - \alpha\beta x_n$$

整理该关系式，我们得到

$$x_{n+2} - \alpha x_{n+1} = \beta(x_{n+1} - \alpha x_n)$$

代入 $t_n = x_{n+1} - \alpha x_n$ ，此式变为

$$t_{n+1} = \beta t_n$$

其通解由 (7.8) 可得，为 $t_n = C\beta^n$ 其中 $C$ 为任意常数。

于是

$$x_{n+1} - \alpha x_n = C\beta^n$$

利用例 7.15(c) 和 (d) 的结果，它具有通解

$$x_n = \begin{cases} C\beta^n/(\beta - \alpha) + A\alpha^n, & \alpha \neq \beta \ Cn\alpha^{n-1} + A\alpha^n, & \alpha = \beta \end{cases}$$

由于 $C$ 为任意常数，我们可以将其改写为更简洁的形式

$$x_n = \begin{cases} A\alpha^n + B\beta^n, & \alpha \neq \beta \ A\alpha^n + Bn\alpha^n, & \alpha = \beta \end{cases} \quad (7.13)$$

其中 $A$ 和 $B$ 是任意常数。因此 (7.13) 给出了 (7.12) 的通解，其中 $\alpha$ 和 $\beta$ 是方程的根

$$\lambda^2 = a\lambda + b$$

这称为该递推关系的特征方程；希腊字母 lambda $\lambda$ 被用作未知数以代替 $x$ 以避免混淆。

例 7.18

求斐波那契递推关系的解

$$x_{n+2} = x_{n+1} + x_n$$

给定 $x_0 = 1$ , $x_1 = 1$ 。

解 该递推关系的特征方程为

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

其根为 $\lambda_1 = (1 + \sqrt{5})/2$ 和 $\lambda_2 = (1 - \sqrt{5})/2$ 。

因此其通解为

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