如何求解递推关系（差分方程）
概念
卡塔兰数： $\dfrac{\operatorname{C}_{2n}^n}{n+1}$ （推荐阅读：https://blog.csdn.net/chlele0105/article/details/38739919）
题型
下文线性其次简称 LH，懒得打字~
递推关系构造模型
P427
【例子】 汉诺塔问题。有柱子 A，B，C。开始时 A 上从下到上按从大到小串着 $n$ 个盘子，B，C 上没有串着盘子。将柱子 A 上的 $n$ 个盘子移动到柱子 C，每次只能移动一个盘子，最少需要多少步骤？
【分析与解答】 假设移动 $n$ 个盘子要 $H_n$ 次，那么移动 $n-1$ 个盘子要 $H_{n-1}$ 次。
记 $b$ 表示 A 的最下面的盘子。
据此，先移动 $b$ 上的 $n-1$ 个盘子，到柱子 B，（需要 $H_{n-1}$ 次）
再移动 $b$ 到柱子 C（需要 $1$ 次）
再移动 B 柱子上的 $n-1$ 个句子到柱子 C 的 $b$ 上。（需要 $H_{n-1}$ 次）
把三个操作的次数加起来，可知：
$$ H_n = 2H_{n-1} + 1 $$求解递推关系：
$$ \begin{aligned} &\begin{aligned} H_{n} &=2 H_{n-1}+1 \\ &=2\left(2 H_{n-2}+1\right)+1=2^{2} H_{n-2}+2+1 \\ &=2^{2}\left(2 H_{n-3}+1\right)+2+1=2^{3} H_{n-3}+2^{2}+2+1 \end{aligned}\\ &\cdots \\ &=2^{n-1} H_{1}+2^{n-2}+2^{n-3}+\cdots+2+1\\ &\begin{array}{l} =2^{n-1}+2^{n-2}+\cdots+2+1 \\ =2^{n}-1 \end{array} \end{aligned} $$【例子】 不含两个连续 0 的 $n$ 位二进制字符串有多少个
【分析与解答】
方便起见，记“不含两个连续 0 的 $n$ 位二进制字符串” 为 $str(n)$
假设 $str(n)$ 有 $H_n$ 个，则 $str(n-1)$ 有 $H_{n-1}$ 个，则 $str(n-2)$ 有 $H_{n-2}$ 个。
而 $str(n) = str(n-1) \sim 1$ 或者 $str(n) = str(n-1)_{\text{且不以0结尾}} \sim 0$ （其中** $\sim$ 表示字符串连接**）
而 $str(n-1)_{\text{且不以0结尾}} = str(n-2) \sim 1$
所以满足条件的字符串的构成有且只有两种形式：$str(n) = str(n-1) \sim 1$ 或者 $str(n) = str(n-2) \sim 1$
我们把满足这两种形式的字符串数量加起来，就能得到递推方程
所以说 $H_n = H_{n-1} + H_{n-2}$
另外，显然 $H_1 = 1, H_2 = 3$，利用上面_求解二阶线性递推式的方法_可得答案。
解常系数、线性、齐次递推关系
【例子】 已知 $a_1 = 1, a_2 = 2, a_n = 5a_{n-1} + 6a_{n-2}\ (n \leqslant 3)$ ,求 $a_n$ 通项。
【分析与解答】
特征方程为： $x^2 = 5x + 6$ ，即 $x^2 - 5x - 6 = (x+1)(x-6) = 0$ ，根为 $x_1 = -1, x_2 = 6$
带入： $\begin{array}{l} a_{n+1}-x_{1} a_{n}=x_{2}\left(a_{n}-x_{1} a_{n-1}\right) \\ a_{n+1}-x_{2} a_{n}=x_{1}\left(a_{n}-x_{2} a_{n-1}\right) \end{array}$ 得到：
$\begin{array}{l} & a_{n+1} + a_n = 6(a_n + a_{n-1})\\ & \Rightarrow a_{n+1} + a_n = 3 \cdot 6 ^{n-1}\\ \end{array}$
$\begin{array}{l} & a_{n+1} -6 a_n = -1(a_n -6 a_{n-1})\\ & \Rightarrow a_{n+1} -6 a_n = -4 \cdot (-1)^{n-1}\\ \end{array}$
联立两个等比数列的方程，消去 $a_{n+1}$ ，可得：
$a_n = \dfrac{3 \cdot 6 ^{n-1}-4 \cdot (-1)^{n-1}}{7}$
方法二
$a_n$ 的解满足如下格式：
$$ a_n = k_1 \cdot (-1)^n + k_2 \cdot 6^n $$带入初始条件
$$ \left\{\begin{array}{cc} a_1 &= 1 = -k_1 + 6k_2\\ a_2 &= 2 = k_1 + 36k_2 \end{array}\right. $$解出 $k_1, k_2$ 。
可以得到同样的结果。这种方法对于更高阶同样有效。
【例子】找出一个斐波那契数的通项公式。
【分析与解答】7th P437
解常系数、线性、_非_齐次递推关系
【例子】求递推关系 $a_n=3a_{n-1}+2n$ 的所有解。具有 $a_1=3$ 的解是什么?
【套路】解出相伴 LH 方程的解和 $a_n = p_n$ 时的解，两个加起来就是整个的解。
【分析与解答】
首先相伴的 LH：$a_n = 3a_{n-1}$ 特征方程 $x^2 = 3x$ 解为 $x = 3 \vee x = 0$，解形式为 $a 3^n$。
针对 $f(n) = 2n$，设多项式 $p_n = bn+c$ 是一个解，带入递推方程：
$$ (bn+c) = 3[b(n-1)+c]+2n\\ \Rightarrow bn+c = 3(bn-b+c)+2n\\ \Rightarrow bn+c = 3bn-3b+3c+2n\\ \Rightarrow (b-3b-2)n + c+3b-3c = 0\\ \Rightarrow (-2-2b)n+3b-2c = 0 $$即 iff $-2-2b = 0 \wedge 3b-2c = 0$ 时是解。也即 $b = -1, c = -\dfrac{3}{2}$。
解的形式为：
$$ a_n = a3^n + p_n = a3^n - n- \dfrac{3}{2} $$当 $a_1 = 3$ 时：可以确定 $3 = 3a-1-3/2$，i.e. $a = 11/6$，故
$$ a_n = \dfrac{11}{6}3^n - n - \dfrac{3}{2} $$【总结】
定理 6：$关于a_n， a_{n-\text{something}} 的多项式 + F(n) = a_n$ 的多项式，如果 $F(n)$ 是 $s^n$ 乘以一个 $n$ 的多项式，则存在的特解形式，也是 $s^n$ 乘以一个 $n$ 的多项式，最大次数和 $F(n)$ 的最大次数相同。
| $f(n)$ | $a_n^{(p)}$ 的形式 |
|---|---|
| $kn$ | $k_1n+k_2$ |
| $d^n$ | $k_1d^n$ |
| $(k_1n+k_2+\cdots)d^n$ | 用定理 6 |
| 比高数的简单吧，三角函数的不考。 |
参考
线性差分方程