浅谈 OI 中常用的一些生成函数运算的合法与正确性

在 OI 中会用到很多生成函数运算…比如求逆（本文中均指乘法逆，而非复合逆）、$\exp$、$\ln$、牛顿迭代、微积分、拉格朗日反演等。

那么就会有很多问题，比如：

1. 求逆（指乘法逆），$\ln,\exp$ 等生成函数运算在什么时候有定义？
2. 这些运算为什么满足我们所期待的性质，如 $\ln\exp A=A,\exp(A+B)=\exp A\cdot\exp B$？
3. 如果你了解过一些（分析意义上的）级数，你可能还会疑惑为什么会存在 $\sum_n n!x^n$ 这种东西（因为它只在 $x=0$ 时收敛）…

归根结底，我们所疑惑的关键在于：为什么可以对这些东西做这些运算？

好的，现在让我们忘记所谓“函数”，而只用一个序列来定义幂级数。

1. 定义及基础运算

定义一个 形式幂级数 （以下简称幂级数）为一个形如 $a_0+a_1x+a_2x^2+\dots$ 形式的表达式。 （注意，这里只有形式：你不需要在意它具体表达什么。）
而序列 $\{a_n\}$ 称为其 系数序列 。称两个幂级数 相等 当且仅当它们的系数序列相同。

为简便，记 $[x^n]f(x)$ 表示幂级数 $f$ 的 $n$ 次项系数。另外，也用 $f(0)$ 表示 $f$ 的 $0$ 次项系数。

我们可以对其做一些运算，例如 加法 或 减法。其定义是

$\sum_n a_n x^n \pm \sum_n b_n x^n = \sum_n (a_n \pm b_n) x^n$

幂级数的乘法由卷积来定义，即

$\left(\sum_n a_n x^n \right) \left(\sum_n b_n x^n \right) = \sum_n c_n x^n\quad(c_n = \sum_k a_k b_{n-k})$

现在你可以验证其满足各种我们所熟知的规律，比如加法交换律、加法结合律、乘法交换/结合律、乘法分配律等等（因此它们构成了一个环）。这些都很简单留作习题。

等下，说好的四则运算呢？还差一个除法…显然要定义除法，只需要定义逆元即 $f^{-1}$。但是有些幂级数是不可能有逆元的，比如首项系数为 $0$ 的幂级数。事实上这也是充要条件，即

命题 1

幂级数 $f(x) = \sum_n a_n x^n$ 存在逆元当且仅当 $a_0 \neq 0$。

证明：必要性很简单，因为若 $a_0 = 0$ 那么 $f$ 与任何幂级数的乘积的零次项系数都是 $0$。

设 $f^{-1} = \sum_n b_n x^n$，那么 $f \cdot f^{-1} = 1$ 相当于说 $\sum_k a_k b_{n-k} = [n=0]$，于是只需要

$b_n = \frac{1}{a_0}\left( [n=0] - \sum_{k>0} a_k b_{n-k} \right)$

即可。$\square$

2. 级数及收敛

有的时候我们会遇到幂级数的无穷求和或者无穷乘积，即

$\sum_{n=0}^{\infty} f_n(x) \\ \prod_{n=0}^{\infty} g_n(x)$

这些东西如何定义？什么时候结果是存在的？

考虑无穷求和。令 $S_n(x)$ 表示部分和（即 $\sum_{i=0}^n f_i(x)$），如果随着 $n$ 的增大，$S_n(x)$ 能“收敛”到某个函数 $S(x)$，那么就可以认为无穷和式收敛到 $S(x)$。对于“收敛”，可以这样考虑：如果要计算 $S(x)$ 的前 $k$ 项，而当 $n$ 超过某个 $N$ 的时候 $S_n$ 的前 $k$ 项就固定了下来，那么就可以认为 $S$ 的前 $k$ 项等于 $S_N$ 的前 $k$ 项。如果对于任意大的 $k$ 都存在这样的一个 $N$ ，就可以认为 $S_n$ 是收敛的，把这样计算出来的 $S$ 称作 $\{S_n\}$ 这列幂级数的极限。

形式化的，对于幂级数 $f(x) = \sum_n a_n x^n$，定义 ${\rm ord}(f)$ 表示 $f$ 的最低非 $0$ 项的次数，即 ${\rm ord}(f)=\min\{ i \mid a_i \neq 0\}$；幂级数列 $\{S_n\}$ 收敛 到 $S$ 的定义就是

$\forall k, \exists N, \text{s.t. } \forall n>N, {\rm ord}(S-S_n) > k$

或者

$\lim_{n\to\infty} {\rm ord}(S-S_n)=\infty$

而若给出函数列 $S_n$，它若收敛，则只需要随着 $n$ 的增大，它开头的项固定下来的越来越多，即

$\forall k, \exists N, \text{s.t. } \forall n, m>N, {\rm ord}(S_m-S_n) > k$

可以发现这实际上就是柯西收敛。而且在此可以更一步发现只需要 ${\rm ord}(S_{n+1}-S_n)\to\infty$ 即可，于是在 $S_n = \sum_{i=0}^n f_i$ 的时候无穷和式收敛的充要条件就是

$\lim_{n\to\infty} {\rm ord}(f_n) = \infty$

当无穷和式收敛的时候，我们实际上可以任意交换其求和顺序（任意交换求和顺序是指将无穷项进行重排，但是并不能展开和式中的括号。最简单的例子比如 $(x-x)+(x-x)+\dots=0+0+0+\dots=0$，但是将括号展开就不收敛了）。因为上式等价于对任意的 $k$，${\rm ord}(f_n)<k$ 的项只有有限个，无论如何交换其求和顺序都是不变的。（下面的无穷乘积也是如此）。

对于无穷乘积亦是如此。在大多数情况下只需要考虑 $g_n(0) = 1$ 的情况，此时若令 $S_n(x)$ 表示 $g_n(x)$ 的前缀积，则

$S_{n+1} - S_n = S_n\cdot(g_{n+1}-1)$

由于 $ {\rm ord}(f\dot g)={\rm ord}(f)+{\rm ord}(g) $，于是 ${\rm ord}(S_n)=\sum_{i=0}^n{\rm ord}(g_n)=0$，从而

${\rm ord}(S_{n+1} - S_n) = {\rm ord}(g_{n+1}-1)$

这样的话，无穷乘积的极限存在的充要条件就是

$\lim_{n\to\infty} {\rm ord}(g_n-1) = \infty$

关于幂级数列的收敛，还有一个定义就是运算的 连续性。如果一个一元运算 $T$满足对任意的收敛数列 $\{f_n\} \to F$，都有 $\lim_{n\to\infty}T(f_n)=T(f)$，那么称 $T$ 是连续的。类似的，如果有一个二元运算 $T(f,g)$，当任意固定 $f$ 时其对 $g$ 是连续的、任意固定 $g$ 时其对 $f$ 是连续的，那么就称它是连续的。

幂级数的四则运算（在有定义时）都是连续的；特别的，我们有

$\begin{aligned} {\rm ord}(f \pm g) &\geq \min({\rm ord}(f), {\rm ord}(g)) \\ {\rm ord}(fg) &= {\rm ord}(f) + {\rm ord}(g) \\ {\rm ord}(1/f-1/g) &= {\rm ord}(f-g) \end{aligned}$

3. 幂级数的复合

对于幂级数的 复合 $f(g(x))$，可以直接定义

$(f \circ g)(x) = f(g(x)) = \sum_n a_n g^n(x)$

其中 $\{a_n\}$ 是 $f$ 的系数序列。可以发现，上式有定义（即收敛）当且仅当 $f$ 是有限的（多项式）或者 $g(0)=0$。

一个幂级数 $g(x)$ 的 复合逆 定义为另一个幂级数 $g^{<-1>}(x)$，使得

$g^{<-1>}(g(x)) = g(g^{<-1>}(x)) = x$

如果展开幂级数复合的式子，可以得到这么一个东西：

$(f \circ g)(x) = \sum_n x^n \sum_k f_k \sum_{a_1+a_2+\dots+a_k=n} g_{a_1} g_{a_2} \cdots g_{a_k}$

…不过这大概不会有什么用处。

通过这个式子可以验证复合的结合律（注意，生成函数不是真正的“函数”，所谓“复合”只是我们所定义的一个运算，所以不能认为其直接和函数一样具有结合律），但是很麻烦。相对的，有一个简洁得多的证法。

命题 2

幂级数的复合存在结合律，即 $(f \circ g) \circ h = f \circ (g \circ h)$。

首先我们需要几个容易验证的命题，比如：

$\begin{aligned} ((f \pm g) \circ h) &= (f \circ h) \pm (g \circ h)\\ ((f \cdot g) \circ h) &= (f \circ h) \cdot (g \circ h)\\ (f^n \circ g) &= (f \circ g)^n\\ {\rm ord}(f \circ g) &= {\rm ord}(f) \cdot {\rm ord}(g)\\ \lim_{n\to\infty} (f_n \circ g) &= (\lim_{n\to\infty} f_n) \circ g \end{aligned}$

其中后两个式子假定 $g(0)=0$，前三个式子只要求函数复合有定义即可（即，$f$ 为多项式或 $g(0)=0$）；前两式都是可以直接验证的，而第三式可以由第二式得来；对于第五个式子，设 $f_n$ 的极限为 $F$，那么随着 $n$ 的增大，${\rm ord}(F(g(x)) - f_n(g(x))) = {\rm ord}((F - f_n) \circ g) = {\rm ord}(F - f_n) \cdot {\rm ord}(g)$ 也会趋近于无穷，因此也是显然可见的（第五个式子说明幂级数复合对 $f$ 是连续的；并且事实上其对 $g$ 也是如此）。

接下来，考虑固定 $g,h$，对任意的 $f$ 求证 $(f \circ g) \circ h = f \circ (g \circ h)$。

首先对 $f(x) = c$ （常数）或者 $f(x) = x$，答案都是显然的；其次，根据上面的前两个式子，可以发现当 $f_1,f_2$ 满足条件时 $f_1 \pm f_2$ 和 $f_1 \cdot f_2$ 也满足条件，因此对于所有可以用常数以及 $x$ 通过有限次加减乘运算得到的 $f$，即任意的多项式，都是满足条件的。

之后对于任意幂级数 $f(x)$，定义 $f_n(x)$ 为它的前 $n$ 项的截断。显然有 $f(x) = \lim_{n\to\infty} f_n(x)$，而无论是 $(f \circ g) \circ h$ 还是 $f \circ (g \circ h)$ 都会保持极限不变，因此既然每个 $f_n$ 都满足两者相等的条件（因为 $f_n$ 是多项式），那么 $f$ 也满足条件。

这样的话，就足以证明函数复合的结合律。$\square$

4. 导数与积分

导数和积分就可以直接仿照分析上的函数来定义，即若 $f(x) = \sum_n a_n x^n$，则

$\begin{aligned} \frac{\mathrm d f(x)}{\mathrm dx} = f'(x) &= \sum_n (n+1)a_{n+1}x^n \\ \int f(x) \mathrm dx &= \sum_{n>0} \frac{a_{n-1}}{n} x^n \end{aligned}$

类似于分析上的函数，同样可以验证微分和积分是逆运算，即

$\begin{aligned} \int f'(x) \mathrm dx &= f(x) + C \\ \frac{\mathrm d}{\mathrm dx} \int f(x) \mathrm dx &= f(x) \end{aligned}$

第一行最后 $+C$ 是因为求导再积分就会把常数项的信息丢失。

并且仍然可以得到求导的各种法则、以及积分的各种法则、和常见函数的微积分。由于公式很多，这里不赘述，但是拿出几个比较复杂的公式。

首先是幂级数复合的求导，即 $\frac{\mathrm d}{\mathrm dx} f(g(x)) = f'(g(x))g'(x)$。对此可以沿用之前证明幂级数复合结合律的方式，通过 $f(x)=c; f(x)=x$ 出发用加减乘以及极限运算证明 $f$ 为任意幂级数的情形。

之后是反函数，即复合逆的求导法则，即 $\frac{\mathrm d}{\mathrm dx} g^{<-1>}(x) = \frac1{g'(g^{<-1>}(x))}$。对此可以考虑

$1 = \frac{\mathrm d}{\mathrm dx} x = \frac{\mathrm d}{\mathrm dx} g(g^{<-1>}x) = g'(g^{<-1>}(x))g^{<-1>\prime}(x)$

即证毕。

其次是积分换元法则，可以写作

$\int f(x) \mathrm dx = (\int f(g(x))g'(x) \mathrm dx) \circ g^{<-1>}$

这个式子可能与原本的式子不一样，但是本质是相同的：等式右侧积分里面的 $x$ 就是换出的新变量 $t\,(x = g(t))$，对其积分得到 $F(t)$ 之后要把 $t$ 用 $x$ 表示出来，从而 $t = g^{<-1>}(x)$，于是原积分即为 $F(g^{<-1>}(x)) = F \circ g^{<-1>}$。

这个法则可以通过两边求导得到，因为两边求导后都是 $f(x)$。至于常数项实际不需要考虑，因为积分出的常数项本来就不固定（可以想象两边都有一个常数 $C$）。

实际上，由于幂级数和通常的实数域上的函数的运算法则几乎完全相同，甚至可以利用同样的方式求解微分方程。

5. 指对函数

对于 $\ln,\exp$，我们会对其是否满足我们需要的性质感兴趣。

首先我们验证一些关于 $\exp$ 的恒等式，关键点在于这个最基础的东西。

命题 3

$ \exp(A+B)=\exp(A)\exp(B) $

对此，写出 $\exp$ 的幂级数形式，即

$\exp(x) = \sum_n \frac{x^n}{n!}$

将 $A+B$ 代入并把 $(A+B)^n$ 用二项式定理展开，换一换求和顺序就可以得到要证的式子。$\square$

利用这个可以证明 $\exp(nA)=\exp^n(A)$ 之类的关于指数函数的简单性质。

之后来证明 $\exp$ 和 $\ln$ 是否为逆运算。准确的说，由于 $\ln$ 不是幂级数（$\ln(1+x)$ 才是），我们会关心 $f(x)=\ln(1+x), g(x)=\exp(x)-1$ 是不是复合逆。因为如果它们是复合逆，那么定义 $\ln(A(x)) = \ln(1+ (A(x)-1)) = f(A(x)-1)$ 之后容易证明 $\ln\exp A = A; \exp\ln A = A$（只需要利用幂级数复合的结合性即可）。

命题 4

$\ln(1+(\exp x-1))=x$

对此可以对左右两边求导，左边由于 $\ln'(1+x) = \frac1{1+x}$ 可以直接验证，于是其导数为 $\frac1{1+(\exp x - 1)}\exp'(x)=1$，而右边的导数亦为 $1$；并且常数项都为 $0$，于是证毕。$\square$

对于反过来的 $\exp(\ln(1+x)) = 1+x$ 也可以类似证明，不过有一个比较通用的方法：考虑若 $f(g(x)) = x$，如何证明 $g(f(x)) = x$？

其实不难证明：根据 $f(g(x)) = x$ 即幂级数复合结合律，我们有 $g(f(g(x))) = g(x)$。从而若令 $h(x) = g(f(x)) - x$，那么 $h(g(x)) = 0$。但是若 $h(x)\neq0$，则容易证明 $h(g(x)) \neq 0$（注意到 $g(x)$ 不可能为 $0$）。于是 $h(x)=0$，即 $g(f(x)) = x$。

这个结论告诉我们一个幂级数的“左复合逆”同时也是它的“右复合逆”。

那么 $\ln$ 的一些性质就可以用 $\exp$ 的性质来倒推，在此不再赘述。