$$x_n = f(x_{n-1}, x_{n-2}, \dots, x_1, x_0)$$

在本节中，我们将讨论两种常见的递推关系类型。这些内容将提供足够的背景知识，使我们能够解决更难的问题。

7.4.1 具有常数系数的一阶线性递推关系

这类关系的一般形式为

$$x_{n+1} = ax_n + b_n, \quad n = 0, 1, 2, \dots$$

其中 $a$ 是常数， $b_n$ 是已知数列。最简单的情形出现在当 $b_n = 0$ 时，此时该关系化简为

$$x_{n+1} = ax_n \quad (7.7)$$

这称为齐次关系，其每个解都是形如

$$x_n = Aa^n \quad (7.8)$$

的等比数列。这称为 (7.7) 的通解，因为 $A$ 是一个可以取任意值的常数。要确定 $A$ 的值，我们需要关于该数列的更多信息。例如，如果我们知道 $x_0$ （设 $C$ ）则 $C = Aa^0$ ，由此得到 $A$ 的值。

一个稍难一点的例子是

$$x_{n+1} = ax_n + b \quad (7.9)$$

其中 b 和 a 一样也是常数。

如果数列的首项如前面一样是 $x_0 = C$ ，那么

$$x_1 = aC + b$$

$$x_2 = ax_1 + b = a(aC + b) + b = Ca^2 + b(1 + a)$$

$$x_3 = ax_2 + b = a[Ca^2 + b(1 + a)] + b = Ca^3 + b(1 + a + a^2)$$

，依此类推。

一般地，我们得到

$$x_n = Ca^n + \left(\frac{1-a^n}{1-a}\right)b, \quad a \neq 1$$

整理后，可以将其表示为

$$x_n = Aa^n + \frac{b}{1-a}, \quad a \neq 1 \quad (7.10)$$