生成函数学习笔记

· · 个人记录

概念

对于数列a_n来说，生成函数是一种形式幂级数，项的系数蕴含了数列的信息。

普通生成函数

将数列\left< a_n \right>的生成函数记作

G(\left<a_n\right>;x) = \sum_{n = 0}^{\infty}a_n x^n

通过观察式子，可以得到简单序列的生成函数

G(\left< 0, 0, \dots, 0, k, 0, \dots \right>;x) = kx^m

但是形如这样的生成函数用途并不够广泛，相较于无穷级数，我们更偏好于封闭形式比如对于序列

a_n = c^n

推导它的生成函数的封闭形式：

令g(z)为a_n的生成函数，对于无穷级数，惯用错位法，利用无穷消去无穷：

g(z) = czg(z) + 1 (1 - cz)g(z) = 1 g(z) = \frac{1}{1 - cz}

很简单，不是吗？下面来推导一个不那么简单的例子

斐波那契数列通项公式

首先将斐波那契数列的递推式写出来

g_n = g_{n - 1} + g_{n - 2}

具体数学直觉告诉我们有哪里不对。带入n = 1尝试发现

g_1 = g_0 + g_{-1}

在这里，由于不关心负数处使得斐波那契数列的负数处取得0。

可能有人会想要将令负数不等于0以解决g_1的问题，但事实上，如果在负数方向无限延申出非零值，那么就不符合生成函数的定义了，注意，生成函数在一端有限，以保证其在一定数域上收敛。

回到问题本身，为了解决g_1处的边界问题，可以加上一个修正

g_n = g_{n - 1} + g_{n - 2} + [n = 1]

就解决了问题

下面展开推导：

令G(z)为斐波那契数列的生成函数

G(z) = zG(z) + z^2G(z) + z

整理一下：

G(z) = \frac{z}{1 - z - z^2} 观察一下所要操作的斐波那契数列本身，我们联想到另外一个递推式$f_n = kf_{n - 1}$，当$f_0 = 1$时，有$f_n = 2 ^n$，对比两个数列，发现斐波那契数列的增长形式和这个数列很像，猜想斐波那契数列也是呈现指数增长的。 以这个为指导，来进行变形： 首先，有$f_n$的生成函数为 $$ G(\left<f_n\right>;x) = \frac{1}{1 - kx} $$ 向这个方向变形： 考虑到需要分母形如$1 - cz$形式的式子，首先对$G(z)$分母部分进行因式分解： $$ \phi = \frac{1 + \sqrt{5}}{2}, \hat\phi = \frac{1 - \sqrt{5}}{2} $$ $$ G(z) = \frac{z}{(1 - \phi z)(1 - \hat\phi z)} $$ 两个所需要的式子在分母上积起来了，我们裂项打开 $$ G(z) = \frac{1}{\sqrt{5}}(\frac{1}{1 - \phi z} - \frac{1}{1 - \hat\phi z}) $$ 好像拿到想要的形式了，展开中间的分式成等比数列的形式，在还原回去，我们就可以得到斐波那契数列的通项公式了 $$ g_n = \frac{\phi^n - {\hat\phi}^n}{\sqrt{5}} $$ 除此之外，对于$G(z)$展开成麦克劳林级数也能达到目的。