【线性代数】生成函数在非常系数与非齐次的线性递推关系的应用(编辑中)

前言

我们之前说了 k 阶常系数线性递推方程的解法,可以使用特征方程求解。今天我们就来学习以下有关于生成函数的内容,它是一种在组合数学和离散数学中非常有用的工具,用于处理序列和计数问题。它可以将序列转换成多项式,从而使得处理序列的操作变得更加方便。在解决非齐次线性递推关系(也称为线性递推方程)时,生成函数可以提供一种有效的方法。

生成函数

概念

生成函数本身不代表什么特殊意义,生成函数是无限的,对其求解是无意义的,它仅仅作为一个工具来使用。

生成函数是一个形式幂级数,通常用来表示一个数列的各项。生成函数的一般形式如下:

$$ F(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots $$

其中,$a_0, a_1, a_2, \ldots$ 是数列的各项,$x$ 是一个变量。生成函数可以是有限的(当数列是有限项时)或无限的(当数列有无穷多项时)。同时我们也可以看到,函数中的自变量  $x$  好像并没有什么意义,他的取值并不影响序列的表示,因此我们称这种函数为形式幂级数

那么这时候就有小伙伴要问了,既然生成函数本身是一个无限长的函数,那么我们要如何使用它呢?

其实很简单,我们前面说了,生成函数可以将序列转换成多项式,那么如果我们能够计算出一个数列的生成函数,我们就可以知道这个数列的通项——也就是说,当我们可以把前面一般形式中的 $a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots$ 表示出来,我们就完成了我们的目标,对于这个无限函数本身来说,这不是我们关心的内容。

应用
1. 序列的计数: 生成函数可以将序列的每一项与幂级数的相应项联系起来。通过操作生成函数,可以进行加法、乘法等操作,从而获得序列的某些性质,如总项数、平均值等。
2. 组合计数: 生成函数在组合数学中应用广泛。例如,如果我们有若干种物品,每种物品有不同的数量,我们可以使用生成函数来计算不同方式选择这些物品的总数。
3. 解决递推关系: 对于线性递推关系,生成函数可以转化为一个多项式方程,从而帮助我们求解递推关系中的项。形式幂级数在齐次递推关系中,生成函数的转化可以非常直接。对于非齐次递推关系,我们可以将问题转化为齐次递推关系的形式,然后使用特定的技巧来解决。


在常数性齐次递推中

之前我们说了,在这种一般情况下,我们使用特征方程可以求出其通项,我们今天尝试使用生成函数解决此类问题。

我们要构建生成函数 $H(x)$,使其满足递推关系。首先,将每一项 $h_n$ 与 $x^n$ 相关联:

$$H(x) = h_0 + h_1 x + h_2 x^2 + h_3 x^3 + \ldots$$

然后考虑我们已知的递推关系:$h_n = 5h_{n-1} + 6h_{n-2}$,可以写出下面三个函数。

$$ \begin{aligned} H(x) &= h_0 + &h_1 x& + &h_2 x^2& + &h_3 x^3& + &h_4 x^4& + &h_5 x^5&+\ldots \ 5xH(x) &= &5h_0x& + &5h_1 x^2& + &5h_2 x^3& + &5h_3 x^4& + &5h_4 x^5&+\ldots \ 6x^2H(x) &= &&&6h_0x^2& + &6h_1 x^3& + &6h_2 x^4& + &6h_3 x^5&+\ldots \ \end{aligned} $$

因为$h_n = 5h_{n-1} + 6h_{n-2}$,所以我们很容易发现从第三位开始,它们相加都满足$h_n x^n = 5h_{n-1} x^n + 6h_{n-2} x^n$的样子,则可以得到生成函数如下:

$$H(x) = h_0 - 5h_0x + h_1x+ 5xH(x) + 6x^2H(x)$$

那么我们已经有了生成函数方程:

$$H(x) = h_0 - 5h_0x + h_1x+ 5xH(x) + 6x^2H(x)$$

接下来,我们可以整理这个方程,将 $H(x)$ 的项整合在一起:

$$H(x) - 5xH(x) - 6x^2H(x) = h_0 - 5h_0x + h_1x$$

将 $H(x)$ 提取出来,得到:

$$(1 - 5x - 6x^2)H(x) = h_0 - 5h_0x + h_1x$$

现在,我们可以将方程两边除以 $(1 - 5x - 6x^2)$,从而求解出最终的生成函数 $H(x)$:

$$H(x) = \frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2}$$

我们已经有了最终的生成函数 $H(x)$,接下来的步骤是将其重新展开成幂级数形式,然后找到系数,以得到数列 ${h_n}$ 的通解,让我们继续吧。

首先,我们要分解分母 $1 - 5x - 6x^2$,得到 $(1 - 6x)(1 + x)$。

然后,我们将分式进行部分分解,得到:

$$\frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2} = \frac{A}{1 - 6x} + \frac{B}{1 + x}$$

接下来,我们可以计算系数 $A$ 和 $B$,

$$ \begin{aligned} A(1 + x) + B(1 - 6x) &= h_0 - 5h_0x + h_1x\ A + Ax + B - 6Bx &= h_0 - 5h_0x + h_1x\ \end{aligned} $$

得到:$A = \frac{h_0 + h_1}{7}$;$B = \frac{6h_0 - h_1}{7}$。

然后将分式展开成幂级数的形式:

$$\frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2} = (\frac{h_0 + h_1}{7}) \cdot \frac{1}{1 - 6x} + (\frac{6h_0 - h_1}{7}) \cdot \frac{1}{1 + x}$$

使用几何级数的展开,几何级数的展开公式是:

$$\frac{1}{1 - r} = 1 + r + r^2 + r^3 + \ldots$$

其中,$r$ 是一个实数,通常称为公比。这个级数在 $|r| < 1$ 的情况下是收敛的,即当公比的绝对值小于 1 时,级数的和会收敛到一个有限的值。

如果公比 $r$ 的绝对值大于等于 1,那么级数就会发散,没有有限的和。

对于这个公式,我们简单证明一下:

$$ \begin{aligned} &设\ &S &= 1 + r + r^2 + r^3 + \ldots\ &则\ &rS &= r + r^2 + r^3 + r^4 + \ldots\ &得\ &(1-r)S&=1\ &综上所述 &S=\frac{1}{1 - r} &= 1 + r + r^2 + r^3 + \ldots\ \end{aligned} $$

在生成函数的推导中,几何级数展开经常用于将分式进行展开成幂级数形式。在这种情况下,我们通常需要确保公比 $r$ 的绝对值小于 1,以确保级数收敛。

还有 $1 + r$ 的情况如下:

$$\frac{1}{1 + r} = 1 - r + r^2 - r^3 + \ldots$$

那么我们把原式进行几何数级展开,我们可以得到:

$$(\frac{h_0 + h_1}{7}) \cdot (1 + 6x + 36x^2 + 216x^3 + \ldots) + (\frac{6h_0 - h_1}{7}) \cdot (1 - x + x^2 - x^3 + \ldots)$$

现在,我们将每一项展开并合并:

$$\frac{h_0 + h_1}{7} + \frac{h_0 + h_1}{7} \cdot (6x) + \frac{h_0 + h_1}{7} \cdot (36x^2) + \ldots + \frac{6h_0 - h_1}{7} + \frac{6h_0 - h_1}{7} \cdot (-x) + \frac{6h_0 - h_1}{7} \cdot (x^2) + \ldots$$

将各项整合:

$$\frac{h_0 + h_1}{7} + \frac{6h_0 + 6h_1}{7}x + \frac{36h_0 + 36h_1}{7}x^2 + \ldots + \frac{6h_0 - h_1}{7} - \frac{6h_0 - h_1}{7}x + \frac{6h_0 - h_1}{7}x^2 + \ldots$$

将各项系数与幂次结合,得到合并后的幂级数形式:

$$h_0 + h_1x + \left(6h_0 + 5h_1\right)x^2 + \left(30h_0 + 31h_1\right)x^3\ldots$$

那么它最后的通项公式如下:

$$h_n = (\frac{h_0 + h_1}{7}) \cdot 6^n + (\frac{6h_0 - h_1}{7}) \cdot (-1)^n$$

所以我们实际上是进行了一次展开->合并->展开的过程,刚开始我们定义了一个生成函数,但是由于都是未知项,我们无法直接求得确切值。所以我们通过合并成$\frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2}$的形式,把原先无穷个未知项变成了已知的$h_0$与$h_1$。最后我们再重新展开,就得到了一个可用于求解的幂级数形式。

在常数性非齐次递推中

终于上正片了,在一般情况下,递

via サン猫の時間漂流
 
 
Back to Top