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

前言

我们之前说了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$。最后我们再重新展开，就得到了一个可用于求解的幂级数形式。

在常数性非齐次递推中

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