《组合数学》 §2.2 学习笔记

例 2.2.1 （Hanoi 塔问题）

这个东西都快讲烂了，$h_n = 2^n-1$ 。

一般地，称数列 $\{h_n\}_{n=0}^{\infty}$ 满足 $k$ 阶常系数线性非齐次递推关系，若对所有的 $n \ge k$ 有

$$h_n = a_1 h_{n-1} + a_2h_{n-2} + \cdots a_kh_{n-k} + f(n)$$

其中 $a_k \ne 0~(k \ge 1)$ 为常数，$f(n) \ne 0$ 是关于 $n$ 的函数。

对于线性非齐次递推关系的通解，可以通过求解其其次部分的通解，

再找到一个满足原递推关系的特解来得到，即

线性非齐次递推关系 $=$ 线性齐次递推关系的通解 $+$ 线性非齐次递推关系的一个特解。

其中所谓的“特解”并不唯一，构造方法也不固定。对于一般的 $f(n)$ ，还不知道寻找它的特解的普遍办法，

一般只能用观察猜想特解的形式再用待定系数法来确定系数。

例如，若 $f(n)$ 是 $n$ 的 $t$ 次多项式，可设特解也是 $n$ 的 $t$ 次多项式，即设特解为

$$p_tn^t + p_{t-1}n^{t-1} + \cdots + p_1n + p_0$$

其中 $p_i(0 \le i \le t)$ 为待定系数。若 $f(n) = \alpha\beta^n$ ，其中 $\alpha,\beta$ 为给定的常数，

且 $\beta$ 为对应的齐次递推关系的特征方程的 $e(\ge 0)$ 重根，则特解可设为 $pn^e\beta^n$ ，这里 $p$ 为待定系数。

有了关系递推关系的解的一般形式，再代入初始条件，就能够确定满足初始条件的一般解了。

例 2.2.2

求解线性非齐次递推关系

$$h_n = 6h_{n-1}-9h_{n-2} + 2n,\quad n \ge 2$$

初始条件为 $h_0 = 1,h_1 = 0$ 。

解 先求解原递推关系对应的线性齐次递推关系递推关系

$$A_n = 6A_{n-1} - 9A_{n-2}$$

的通解得到 $A_n = (an + b)3^n$ 。再寻找原线性飞起洗递推关系的一个特解。

观察原递推关系的特解，猜想 $B_n = cn+d$ （其中 $c,d$ 待定）应为一个特解。

代入原递推关系，解得 $c = \frac{1}{2},d = \frac{3}{2}$ ，即 $B_n = \frac{1}{2}n + \frac{3}{2}$ 为一个特解。

故原线性非齐次递推关系的通解可设为

$$h_n = A_n + B_n = (an+b)3^n + \frac{1}{2}n + \frac{3}{2}$$

代入初始条件，解得 $a = -\frac{1}{6},b = -\frac{1}{2}$ ，于是

$$h_n = \left(-\frac{n}{6} - \frac{1}{2}\right)3^n + \frac{1}{2} n + \frac{3}{2}$$

注 2.2.3

注意，必须在有了线性齐次递推关系的通解以及线性非齐次递推关系的特解并将它们相加得到 $A_n + B_n$ 以后

才可以代入初始条件以获得通解的特征根系数。因为初始条件满足线性非齐次递推关系本身而非其齐次部分。