离散数学 - 递推关系

---

---

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

定义

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

示例 - 斐波那契数列 - $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_{n-k}$（$A_n$是常数且$A_k \neq 0$）关于数列作为一阶多项式。

以下是一些线性递推方程的示例：

如何求解线性递推关系

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

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

$$x^2 - Ax - B = 0$$

在求解根的过程中，可能会出现三种情况：

情况1 - 如果此方程因式分解为$(x- x_1)(x- 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\ (因为\ x_1 = 3\ 且\ 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$，即$c.x^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$$

一些应用领域

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

• 用于解决各种计数问题。例如，用面值为1元、2元、5元、10元、20元和50元的纸币兑换100元人民币的方法数

• 用于解决递推关系

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

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

问题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} + \dots$

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

问题2

无限级数的生成函数是什么；$1, 1, 1, 1, \dots$？

解答

这里，$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} +\dots \dots \dots = 1/ (1 - ax)$

• 对于 $a_{k} = (k + 1)$，$G(x) = \sum_{k = 0}^{\infty }(k + 1)x^{k} = 1 + 2x + 3x^{2} \dots \dots \dots =\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}$