铃悬 的博客

铃悬 的博客

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

posted on 2019-05-09 08:18:31 | under 数学 |

本篇文章已经同步发表在 _rqy's Blog。会有后续更新。

在 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. 级数及收敛

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

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

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

考虑无穷求和。令 $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$ 的性质来倒推,在此不再赘述。