_rqy's Blog

一只猫猫,想成为天才少女数学家!

0%

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

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

那么就会有很多问题,比如:

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

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

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

1. 定义及基础运算

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

为简便,记 [xn]f(x)[x^n]f(x) 表示幂级数 ffnn 次项系数。另外,也用 f(0)f(0) 表示 ff00 次项系数。

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

nanxn±nbnxn=n(an±bn)xn\sum_n a_n x^n \pm \sum_n b_n x^n = \sum_n (a_n \pm b_n) x^n

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

(nanxn)(nbnxn)=ncnxn(cn=kakbnk)\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})

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

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

命题 1

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

证明:必要性很简单,因为若 a0=0a_0 = 0 那么 ff 与任何幂级数的乘积的零次项系数都是 00

f1=nbnxnf^{-1} = \sum_n b_n x^n,那么 ff1=1f \cdot f^{-1} = 1 相当于说 kakbnk=[n=0]\sum_k a_k b_{n-k} = [n=0],于是只需要

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

即可。\square

2. 级数及收敛

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

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

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

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

形式化的,对于幂级数 f(x)=nanxnf(x) = \sum_n a_n x^n,定义 ord(f){\rm ord}(f) 表示 ff 的最低非 00 项的次数,即 ord(f)=min{iai0}{\rm ord}(f)=\min\{ i \mid a_i \neq 0\};幂级数列 {Sn}\{S_n\} 收敛SS 的定义就是

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

或者

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

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

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

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

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

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

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

Sn+1Sn=Sn(gn+11)S_{n+1} - S_n = S_n\cdot(g_{n+1}-1)

由于 ord(fg˙)=ord(f)+ord(g){\rm ord}(f\dot g)={\rm ord}(f)+{\rm ord}(g),于是 ord(Sn)=i=0nord(gn)=0{\rm ord}(S_n)=\sum_{i=0}^n{\rm ord}(g_n)=0,从而

ord(Sn+1Sn)=ord(gn+11){\rm ord}(S_{n+1} - S_n) = {\rm ord}(g_{n+1}-1)

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

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

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

幂级数的四则运算(在有定义时)都是连续的;特别的,我们有

ord(f±g)min(ord(f),ord(g))ord(fg)=ord(f)+ord(g)ord(1/f1/g)=ord(fg)\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(g(x)),可以直接定义

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

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

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

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

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

(fg)(x)=nxnkfka1+a2++ak=nga1ga2gak(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

幂级数的复合存在结合律,即 (fg)h=f(gh)(f \circ g) \circ h = f \circ (g \circ h)

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

((f±g)h)=(fh)±(gh)((fg)h)=(fh)(gh)(fng)=(fg)nord(fg)=ord(f)ord(g)limn(fng)=(limnfn)g\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)=0g(0)=0,前三个式子只要求函数复合有定义即可(即,ff 为多项式或 g(0)=0g(0)=0);前两式都是可以直接验证的,而第三式可以由第二式得来;对于第五个式子,设 fnf_n 的极限为 FF,那么随着 nn 的增大,ord(F(g(x))fn(g(x)))=ord((Ffn)g)=ord(Ffn)ord(g){\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) 也会趋近于无穷,因此也是显然可见的(第五个式子说明幂级数复合对 ff 是连续的;并且事实上其对 gg 也是如此)。

接下来,考虑固定 g,hg,h,对任意的 ff 求证 (fg)h=f(gh)(f \circ g) \circ h = f \circ (g \circ h)

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

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

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

4. 导数与积分

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

df(x)dx=f(x)=n(n+1)an+1xnf(x)dx=n>0an1nxn\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}

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

f(x)dx=f(x)+Cddxf(x)dx=f(x)\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+C 是因为求导再积分就会把常数项的信息丢失。

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

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

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

1=ddxx=ddxg(g<1>x)=g(g<1>(x))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)

即证毕。

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

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

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

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

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

5. 指对函数

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

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

命题 3

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

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

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

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

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

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

命题 4

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

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

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

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

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

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