概念
卡塔兰数: $\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}$ 次)
把三个操作的次数加起来,可知:
求解递推关系:
【例子】 不含两个连续 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$ 的解满足如下格式:
带入初始条件
解出 $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$ 是一个解,带入递推方程:
即 iff $-2-2b = 0 \wedge 3b-2c = 0$ 时是解。也即 $b = -1, c = -\dfrac {3}{2}$。
解的形式为:
当 $a_1 = 3$ 时:可以确定 $3 = 3a-1-3/2$,i.e. $a = 11/6$,故
【总结】
定理 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 |
比高数的简单吧,三角函数的不考。 |
参考
线性差分方程