2023.9.4 开摆：二项式反演的gf推法

· · 个人记录

今天学习具体数学 P225 时，用二项式反演推了 (6.40) ，进而发现了 (6.39) 和 (6.40) 这两个式子可以二项式反演互推，而书中是用生成函数推的，想了一下发现这种形式的二项式反演是可以生成函数推出来的。

\begin{aligned} f(m)&=\sum_{k\geq m}\binom{k}{m}g(k)\\ \sum_{m\geq 0} z^mf(m)&=\sum_{m\geq 0}\sum_{k\geq m}\binom{k}{m}g(k)z^m\\ &=\sum_{k\geq 0}g(k)\sum_{m\leq k}\binom{k}{m}z^m\\ &=\sum_{k\geq 0}g(k)(z+1)^k \end{aligned}

换元，用 z-1 替换 z 即得到：

\sum_{k\geq 0}(z-1)^kf(k)=\sum_{k\geq 0}g(k)z^k

两边提取 [z^m] 系数得到：

g(m)=\sum_{k\geq m}\binom{k}{m}(-1)^{k-m}f(k)

这里的思路在于用在 f 的 ogf F(z) 中换元 z\gets z-1 得到 g 的 ogf G(z)，另一个方向的二项式反演是否还能用 ogf 换元的方式得到还在思考emmm

原来学过，现在要证：

f(m)=\sum_{k\leq m}\binom{m}{k}g(k)\Longleftrightarrow g(m)=\sum_{k\leq m}\binom{m}{k}(-1)^{m-k}f(k)

令 F,G 为 f,g 的 egf，那么就有 F(z)=G(z)\times e^z，等价于 G(z)=F(z)e^{-z}，展开之后就是上式。