离散数学 - 递归关系

---

在本章中，我们将讨论递归技术如何导出序列并用于解决计数问题。以递归方式查找序列项的过程称为递归关系。我们研究线性递推关系的理论及其解决方案。最后，我们引入用于求解递推关系的生成函数。

定义

递归关系是一个递归定义序列的方程，其中下一项是前一项的函数（将 $F_n$ 表示为 $F_i$ 与 $i < n$ 的某种组合）。

示例− 斐波那契数列 − $F_n = F_{n-1} + F_{n-2}$，河内塔 − $F_n = 2F_{n-1} + 1$

线性递推关系

k 次或 k 阶线性递推方程的格式为 $x_n= A_1 x_{n-1}+ A_2 x_{n-1}+ A_3 x_{n-1}+ \dots A_k x_ {nk} $($A_n$ 是常数，$A_k \neq 0$) 作为一次多项式的数字序列。

这些是线性递推方程的一些例子 -

如何求解线性递推关系

假设二阶线性递推关系为 − $F_n = AF_{n-1} +BF_{n-2}$，其中 A 和 B 是实数。

上述递推关系的特征方程为 -

$$x^2 - 斧头 - B = 0$$

寻找根源时可能会发生三种情况 -

情况 1 - 如果该方程因式分解为 $(xx- x_1)(xx- x_1) = 0$ 并且产生两个不同的实根 $x_1$ 和 $x_2$，则 $F_n = ax_1^n+ bx_2^n$ 是解决方案。[这里，a和b是常数]

情况 2 - 如果该方程分解为 $(x- x_1)^2 = 0$ 并且产生单实根 $x_1$，则 $F_n = a x_1^n+ bn x_1^n$ 就是解。

情况 3 - 如果方程产生两个不同的复数根，极坐标形式的 $x_1$ 和 $x_2$ $x_1 = r \angle \theta$ 和 $x_2 = r \angle(- \theta)$，则 $F_n = r ^n (a cos(n\theta)+ b sin(n\theta))$ 是解。

问题1

求解递推关系 $F_n = 5F_{n-1} - 6F_{n-2}$，其中 $F_0 = 1$ 且 $F_1 = 4$

解决方案

递推关系的特征方程为 -

$$x^2 - 5x + 6 = 0,$$

所以，$(x - 3) (x - 2) = 0$

因此，根是 -

$x_1 = 3$ 和 $x_2 = 2$

根源是真实而独特的。所以，这是案例 1 的形式

因此，解决方案是 -

$$F_n = ax_1^n + bx_2^n$$

这里，$F_n = a3^n + b2^n\ (As\ x_1 = 3\ and\ x_2 = 2)$

所以，

$1 = F_0 = a3^0 + b2^0 = a+b$

$4 = F_1 = a3^1 + b2^1 = 3a+2b$

求解这两个方程，我们得到 $a = 2$ 和 $b = -1$

因此，最终的解决方案是 -

$$F_n = 2.3^n + (-1) 。2^n = 2.3^n - 2^n $$

问题2

求解递推关系 − $F_n = 10F_{n-1} - 25F_{n-2}$，其中 $F_0 = 3$ 且 $F_1 = 17$

解决方案

递推关系的特征方程为 -

$$ x^2 - 10x -25 = 0$$

所以 $(x - 5)^2 = 0$

因此，有一个实根 $x_1 = 5$

由于存在单个实值根，因此采用情况 2 的形式

因此，解决方案是 -

$F_n = ax_1^n + bnx_1^n$

$3 = F_0 = a.5^0 + (b)(0.5)^0 = a$

$17 = F_1 = a.5^1 + b.1.5^1 = 5a+5b$

求解这两个方程，我们得到 $a = 3$ 和 $b = 2/5$

因此，最终的解决方案是 - $F_n = 3.5^n +( 2/5) .n.2^n $

问题3

求解递推关系 $F_n = 2F_{n-1} - 2F_{n-2}$，其中 $F_0 = 1$ 且 $F_1 = 3$

解决方案

递推关系的特征方程为 -

$$x^2 -2x -2 = 0$$

因此，根是 -

$x_1 = 1 + i$ 和 $x_2 = 1 - i$

以极坐标形式，

$x_1 = r \angle \theta$ 和 $x_2 = r \angle(- \theta),$ 其中 $r = \sqrt 2$ 和 $\theta = \frac{\pi}{4}$

根是虚构的。因此，这就是案例 3 的形式。

因此，解决方案是 -

$F_n = (\sqrt 2 )^n (a cos(n .\sqcap /4) + b sin(n .\sqcap /4))$

$1 = F_0 = (\sqrt 2 )^0 (a cos(0 .\sqcap /4) + b sin(0 .\sqcap /4) ) = a$

$3 = F_1 = (\sqrt 2 )^1 (a cos(1 .\sqcap /4) + b sin(1 . \sqcap /4) ) = \sqrt 2 ( a/ \sqrt 2 + b/ \sqrt 2 )$

求解这两个方程，我们得到 $a = 1$ 和 $b = 2$

因此，最终的解决方案是 -

$F_n = (\sqrt 2 )^n (cos(n .\pi /4 ) + 2 sin(n .\pi /4 ))$

非齐次递推关系及特解

如果递归关系具有以下形式，则称为非齐次关系

$F_n = AF_{n-1} + BF_{n-2} + f(n)$ 其中 $f(n) \ne 0$

其相关的齐次递推关系为 $F_n = AF_{n–1} + BF_{n-2}$

非齐次递推关系的解 $(a_n)$ 有两部分。

第一部分是相关齐次递推关系的解 $(a_h)$，第二部分是特定解 $(a_t)$。

$$a_n=a_h+a_t$$

第一部分的解决方案是使用上一节中讨论的过程完成的。

为了找到特定的解决方案，我们找到合适的试验解决方案。

设 $f(n) = cx^n$ ；令 $x^2 = Ax + B$ 为相关齐次递推关系的特征方程，并令 $x_1$ 和 $x_2$ 为其根。

• 如果 $x \ne x_1$ 和 $x \ne x_2$，则 $a_t = Ax^n$

• 如果 $x = x_1$、$x \ne x_2$，则 $a_t = Anx^n$

• 如果 $x = x_1 = x_2$，则 $a_t = An^2x^n$

例子

设非齐次递推关系为 $F_n = AF_{n–1} + BF_{n-2} + f(n)$，特征根为 $x_1 = 2$ 和 $x_2 = 5$。$f(n)$ 不同可能值的试验解决方案如下 -

问题

求解递推关系 $F_n = 3F_{n-1} + 10F_{n-2} + 7.5^n$，其中 $F_0 = 4$ 且 $F_1 = 3$

解决方案

这是线性非齐次关系，其中关联的齐次方程为 $F_n=3F_{n-1}+10F_{n-2}$ 和 $f(n)=7.5^n$

其相关齐次关系的特征方程为 -

$$x^2 - 3x -10 = 0$$

或者，$(x - 5)(x + 2) = 0$

或者，$x_1= 5$ 且 $x_2 = -2$

因此 $a_h = a.5^n + b.(-2)^n$ ，其中 a 和 b 是常量。

由于 $f(n) = 7.5^n$，即形式为 $cx^n$，at 的合理尝试解为 $Anx^n$

$a_t = Anx^n = An5^n$

将解代入递推关系后，我们得到 -

$An5^n = 3A(n – 1)5^{n-1} + 10A(n – 2)5^{n-2} + 7.5^n$

两边除以 $5^{n-2}$，我们得到

$An5^2 = 3A(n - 1)5 + 10A(n - 2)5^0 + 7.5^2$

或者，$25An = 15An - 15A + 10An - 20A + 175$

或者，$35A = 175$

或者，$A = 5$

所以，$F_n = An5^n= 5n5^n=n5^{n+1}$

递推关系的解可以写为 -

$F_n = a_h + a_t$

$=a.5^n+b.(-2)^n+n5^{n+1}$

将 $F_0 = 4$ 和 $F_1 = 3$ 代入上式中，我们得到 $a = -2$ 和 $b = 6$

因此，解决方案是 -

$F_n = n5^{n+1} + 6.(-2)^n -2.5^n$

生成函数

生成函数表示序列，其中序列的每一项都表示为形式幂级数中变量 x 的系数。

从数学上讲，对于无限序列，例如 $a_0, a_1, a_2,\dots, a_k,\dots,$ 生成函数将是 -

$$G_x=a_0+a_1x+a_2x^2+ \dots +a_kx^k+ \dots = \sum_{k=0}^{\infty}a_kx^k$$

一些应用领域

生成函数可用于以下目的 -

• 用于解决各种计数问题。例如，兑换卢比的方式有多种。100 卢比纸币，面额为 1 卢比、2 卢比、5 卢比、10 卢比、20 卢比和 50 卢比

• 用于解决递归关系

• 用于证明一些组合恒等式

• 用于查找序列项的渐近公式

问题1

序列 $\lbrace {a_k} \rbrace$ （其中 $a_k = 2$ 和 $a_k = 3k$）的生成函数是什么？

解决方案

当$a_k = 2$时，生成函数$G(x) = \sum_{k = 0}^{\infty }2x^{k} = 2 + 2x + 2x^{2} + 2x^{3} + \点$

当 $a_{k} = 3k 时，G(x) = \sum_{k = 0}^{\infty }3kx^{k} = 0 + 3x + 6x^{2} + 9x^{3} + \dots \点$

问题2

无穷级数的生成函数是什么？$1, 1, 1, 1, \点$?

解决方案

这里，$a_k = 1$，对于 $0 \le k \le \infty$

因此，$G(x) = 1 + x + x^{2} + x^{3}+ \dots \dots= \frac{1}{(1 - x)}$

一些有用的生成函数

• 对于 $a_k = a^{k}，G(x) = \sum_{k = 0}^{\infty }a^{k}x^{k} = 1 + ax + a^{2}x^{ 2} +\点 \点 \点 = 1/ (1 - 斧头)$

• 对于 $a_{k} = (k + 1)，G(x) = \sum_{k = 0}^{\infty }(k + 1)x^{k} = 1 + 2x + 3x^{2} \点 \点 \点 =\frac{1}{(1 - x)^{2}}$

• 对于 $a_{k} = c_{k}^{n}，G(x) = \sum_{k = 0}^{\infty} c_{k}^{n}x^{k} = 1+c_ {1}^{n}x + c_{2}^{n}x^{2} + \dots \dots \dots + x^{2} = (1 + x)^{n}$

• 对于 $a_{k} = \frac{1}{k!}，G(x) = \sum_{k = 0}^{\infty }\frac{x^{k}}{k!} = 1 + x + \frac{x^{2}}{2!} + \frac{x^{3}}{3!}\dots \dots \dots = e^{x}$