【线性代数】生成函数在非常系数与非齐次的线性递推关系的应用(编辑中) 我们之前说了 k 阶常系数线性递推方程的解法，可以使用特征方程求解。今天我们就来学习以下有关于生成函数的内容，它是一种在组合数学和离散数学中非常有用的工具，用于处理序列和计数问题。它可以将序列转换成多项式，从而使得处理序列的操作变得更加方便。在解决非齐次线性递推关系（也称为线性递推方程）时，生成函数可以提供一种有效的方法。
生成函数# 生成函数本身不代表什么特殊意义，生成函数是无限的，对其求解是无意义的，它仅仅作为一个工具来使用。
生成函数是一个形式幂级数，通常用来表示一个数列的各项。生成函数的一般形式如下：
F ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + … F(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots F ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + … 其中，a 0 , a 1 , a 2 , … a_0, a_1, a_2, \ldots a 0 , a 1 , a 2 , … x x x x x x 形式幂级数 。
那么这时候就有小伙伴要问了，既然生成函数本身是一个无限长的函数，那么我们要如何使用它呢？
其实很简单，我们前面说了，生成函数可以将序列转换成多项式，那么如果我们能够计算出一个数列的生成函数，我们就可以知道这个数列的通项——也就是说，当我们可以把前面一般形式中的 a 0 + a 1 x + a 2 x 2 + a 3 x 3 + … a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots a 0 + a 1 x + a 2 x 2 + a 3 x 3 + …
序列的计数： 生成函数可以将序列的每一项与幂级数的相应项联系起来。通过操作生成函数，可以进行加法、乘法等操作，从而获得序列的某些性质，如总项数、平均值等。
组合计数： 生成函数在组合数学中应用广泛。例如，如果我们有若干种物品，每种物品有不同的数量，我们可以使用生成函数来计算不同方式选择这些物品的总数。
解决递推关系： 对于线性递推关系，生成函数可以转化为一个多项式方程，从而帮助我们求解递推关系中的项。形式幂级数 在齐次递推关系中，生成函数的转化可以非常直接。对于非齐次递推关系，我们可以将问题转化为齐次递推关系的形式，然后使用特定的技巧来解决。
在常数性齐次递推中# 之前我们说了，在这种一般情况下，我们使用特征方程可以求出其通项，我们今天尝试使用生成函数解决此类问题。
我们要构建生成函数 H ( x ) H(x) H ( x ) h n h_n h n x n x^n x n
H ( x ) = h 0 + h 1 x + h 2 x 2 + h 3 x 3 + … H(x) = h_0 + h_1 x + h_2 x^2 + h_3 x^3 + \ldots H ( x ) = h 0 + h 1 x + h 2 x 2 + h 3 x 3 + …
然后考虑我们已知的递推关系：h n = 5 h n − 1 + 6 h n − 2 h_n = 5h_{n-1} + 6h_{n-2} h n = 5 h n − 1 + 6 h n − 2
H ( x ) = h 0 + h 1 x + h 2 x 2 + h 3 x 3 + h 4 x 4 + h 5 x 5 + … 5 x H ( x ) = 5 h 0 x + 5 h 1 x 2 + 5 h 2 x 3 + 5 h 3 x 4 + 5 h 4 x 5 + … 6 x 2 H ( x ) = 6 h 0 x 2 + 6 h 1 x 3 + 6 h 2 x 4 + 6 h 3 x 5 + … \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 ( x ) 5 x H ( x ) 6 x 2 H ( x ) = h 0 + = = h 1 x 5 h 0 x + + h 2 x 2 5 h 1 x 2 6 h 0 x 2 + + + h 3 x 3 5 h 2 x 3 6 h 1 x 3 + + + h 4 x 4 5 h 3 x 4 6 h 2 x 4 + + + h 5 x 5 5 h 4 x 5 6 h 3 x 5 + … + … + … 因为h n = 5 h n − 1 + 6 h n − 2 h_n = 5h_{n-1} + 6h_{n-2} h n = 5 h n − 1 + 6 h n − 2 h n x n = 5 h n − 1 x n + 6 h n − 2 x n h_n x^n = 5h_{n-1} x^n + 6h_{n-2} x^n h n x n = 5 h n − 1 x n + 6 h n − 2 x n
H ( x ) = h 0 − 5 h 0 x + h 1 x + 5 x H ( x ) + 6 x 2 H ( x ) H(x) = h_0 - 5h_0x + h_1x+ 5xH(x) + 6x^2H(x) H ( x ) = h 0 − 5 h 0 x + h 1 x + 5 x H ( x ) + 6 x 2 H ( x )
那么我们已经有了生成函数方程：
H ( x ) = h 0 − 5 h 0 x + h 1 x + 5 x H ( x ) + 6 x 2 H ( x ) H(x) = h_0 - 5h_0x + h_1x+ 5xH(x) + 6x^2H(x) H ( x ) = h 0 − 5 h 0 x + h 1 x + 5 x H ( x ) + 6 x 2 H ( x )
接下来，我们可以整理这个方程，将 H ( x ) H(x) H ( x )
H ( x ) − 5 x H ( x ) − 6 x 2 H ( x ) = h 0 − 5 h 0 x + h 1 x H(x) - 5xH(x) - 6x^2H(x) = h_0 - 5h_0x + h_1x H ( x ) − 5 x H ( x ) − 6 x 2 H ( x ) = h 0 − 5 h 0 x + h 1 x
将 H ( x ) H(x) H ( x )
( 1 − 5 x − 6 x 2 ) H ( x ) = h 0 − 5 h 0 x + h 1 x (1 - 5x - 6x^2)H(x) = h_0 - 5h_0x + h_1x ( 1 − 5 x − 6 x 2 ) H ( x ) = h 0 − 5 h 0 x + h 1 x
现在，我们可以将方程两边除以 ( 1 − 5 x − 6 x 2 ) (1 - 5x - 6x^2) ( 1 − 5 x − 6 x 2 ) H ( x ) H(x) H ( x )
H ( x ) = h 0 − 5 h 0 x + h 1 x 1 − 5 x − 6 x 2 H(x) = \frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2} H ( x ) = 1 − 5 x − 6 x 2 h 0 − 5 h 0 x + h 1 x
我们已经有了最终的生成函数 H ( x ) H(x) H ( x ) 重新 展开成幂级数形式，然后找到系数，以得到数列 { h n } \{h_n\} { h n }
首先，我们要分解分母 1 − 5 x − 6 x 2 1 - 5x - 6x^2 1 − 5 x − 6 x 2 ( 1 − 6 x ) ( 1 + x ) (1 - 6x)(1 + x) ( 1 − 6 x ) ( 1 + x )
然后，我们将分式进行部分分解，得到：
h 0 − 5 h 0 x + h 1 x 1 − 5 x − 6 x 2 = A 1 − 6 x + B 1 + x \frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2} = \frac{A}{1 - 6x} + \frac{B}{1 + x} 1 − 5 x − 6 x 2 h 0 − 5 h 0 x + h 1 x = 1 − 6 x A + 1 + x B
接下来，我们可以计算系数 A A A B B B
A ( 1 + x ) + B ( 1 − 6 x ) = h 0 − 5 h 0 x + h 1 x A + A x + B − 6 B x = h 0 − 5 h 0 x + h 1 x \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 ( 1 + x ) + B ( 1 − 6 x ) A + A x + B − 6 B x = h 0 − 5 h 0 x + h 1 x = h 0 − 5 h 0 x + h 1 x 得到：A = h 0 + h 1 7 A = \frac{h_0 + h_1}{7} A = 7 h 0 + h 1 B = 6 h 0 − h 1 7 B = \frac{6h_0 - h_1}{7} B = 7 6 h 0 − h 1
然后将分式展开成幂级数的形式：
h 0 − 5 h 0 x + h 1 x 1 − 5 x − 6 x 2 = ( h 0 + h 1 7 ) ⋅ 1 1 − 6 x + ( 6 h 0 − h 1 7 ) ⋅ 1 1 + x \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} 1 − 5 x − 6 x 2 h 0 − 5 h 0 x + h 1 x = ( 7 h 0 + h 1 ) ⋅ 1 − 6 x 1 + ( 7 6 h 0 − h 1 ) ⋅ 1 + x 1
使用几何级数的展开，几何级数的展开公式是：
1 1 − r = 1 + r + r 2 + r 3 + … \frac{1}{1 - r} = 1 + r + r^2 + r^3 + \ldots 1 − r 1 = 1 + r + r 2 + r 3 + …
其中，r r r ∣ r ∣ < 1 |r| < 1 ∣ r ∣ < 1
如果公比 r r r
对于这个公式，我们简单证明一下：
设 S = 1 + r + r 2 + r 3 + … 则 r S = r + r 2 + r 3 + r 4 + … 得 ( 1 − r ) S = 1 综上所述 S = 1 1 − r = 1 + r + r 2 + r 3 + … \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} 设 则 得 综上所述 S r S ( 1 − r ) S S = 1 − r 1 = 1 + r + r 2 + r 3 + … = r + r 2 + r 3 + r 4 + … = 1 = 1 + r + r 2 + r 3 + … 在生成函数的推导中，几何级数展开经常用于将分式进行展开成幂级数形式。在这种情况下，我们通常需要确保公比 r r r
还有 1 + r 1 + r 1 + r
1 1 + r = 1 − r + r 2 − r 3 + … \frac{1}{1 + r} = 1 - r + r^2 - r^3 + \ldots 1 + r 1 = 1 − r + r 2 − r 3 + …
那么我们把原式进行几何数级展开，我们可以得到：
( h 0 + h 1 7 ) ⋅ ( 1 + 6 x + 36 x 2 + 216 x 3 + … ) + ( 6 h 0 − h 1 7 ) ⋅ ( 1 − x + x 2 − x 3 + … ) (\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) ( 7 h 0 + h 1 ) ⋅ ( 1 + 6 x + 36 x 2 + 216 x 3 + … ) + ( 7 6 h 0 − h 1 ) ⋅ ( 1 − x + x 2 − x 3 + … )
现在，我们将每一项展开并合并：
h 0 + h 1 7 + h 0 + h 1 7 ⋅ ( 6 x ) + h 0 + h 1 7 ⋅ ( 36 x 2 ) + … + 6 h 0 − h 1 7 + 6 h 0 − h 1 7 ⋅ ( − x ) + 6 h 0 − h 1 7 ⋅ ( x 2 ) + … \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 7 h 0 + h 1 + 7 h 0 + h 1 ⋅ ( 6 x ) + 7 h 0 + h 1 ⋅ ( 36 x 2 ) + … + 7 6 h 0 − h 1 + 7 6 h 0 − h 1 ⋅ ( − x ) + 7 6 h 0 − h 1 ⋅ ( x 2 ) + …
将各项整合：
h 0 + h 1 7 + 6 h 0 + 6 h 1 7 x + 36 h 0 + 36 h 1 7 x 2 + … + 6 h 0 − h 1 7 − 6 h 0 − h 1 7 x + 6 h 0 − h 1 7 x 2 + … \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 7 h 0 + h 1 + 7 6 h 0 + 6 h 1 x + 7 36 h 0 + 36 h 1 x 2 + … + 7 6 h 0 − h 1 − 7 6 h 0 − h 1 x + 7 6 h 0 − h 1 x 2 + …
将各项系数与幂次结合，得到合并后的幂级数形式：
h 0 + h 1 x + ( 6 h 0 + 5 h 1 ) x 2 + ( 30 h 0 + 31 h 1 ) x 3 … h_0 + h_1x + \left(6h_0 + 5h_1\right)x^2 + \left(30h_0 + 31h_1\right)x^3\ldots h 0 + h 1 x + ( 6 h 0 + 5 h 1 ) x 2 + ( 30 h 0 + 31 h 1 ) x 3 …
那么它最后的通项公式如下：
h n = ( h 0 + h 1 7 ) ⋅ 6 n + ( 6 h 0 − h 1 7 ) ⋅ ( − 1 ) n h_n = (\frac{h_0 + h_1}{7}) \cdot 6^n + (\frac{6h_0 - h_1}{7}) \cdot (-1)^n h n = ( 7 h 0 + h 1 ) ⋅ 6 n + ( 7 6 h 0 − h 1 ) ⋅ ( − 1 ) n
所以我们实际上是进行了一次展开->合并->展开的过程，刚开始我们定义了一个生成函数，但是由于都是未知项，我们无法直接求得确切值。所以我们通过合并成h 0 − 5 h 0 x + h 1 x 1 − 5 x − 6 x 2 \frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2} 1 − 5 x − 6 x 2 h 0 − 5 h 0 x + h 1 x h 0 h_0 h 0 h 1 h_1 h 1
在常数性非齐次递推中# 终于上正片了，在一般情况下，递
