浅谈 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) \]

由于 $ {}(fg)={}(f)+{}(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

$ (A+B)=(A)(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\) 的性质来倒推,在此不再赘述。