概念

卡塔兰数： $\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
比高数的简单吧，三角函数的不考。

参考

线性差分方程

https://www.cnblogs.com/TaigaCon/p/6878674.html