Site Overlay

离散数学:递推关系(差分方程)(Recurrence Relation | Difference Equation )

概念

卡塔兰数: $\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(an + 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(an -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 \or 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 \and 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

发表评论

电子邮件地址不会被公开。 必填项已用*标注