一些乱七八糟的证明

· · 个人记录

看到有一些有趣的式子，不知道出处与名字，就尝试证明一下吧，，

对于序列 \{f_n \}_{n=0}^\infty 的普通生成函数 F(x)，有

[x^n]\frac{1}{1-x}F\left( \frac{x}{1-x}\right)=\sum_{k=0}^n \binom nk f_k

尝试暴力代入

\frac{1}{1-x}F\left( \frac{x}{1-x}\right)=\sum_{k=0}^\infty f_k \frac{x^k}{(1-x)^{k+1}} [x^n] \frac{1}{1-x}F\left( \frac{x}{1-x}\right)=\sum_{k=0}^n f_k [x^{n-k}] \frac{1}{(1-x)^{k+1}} [x^n] \frac{1}{1-x}F\left( \frac{x}{1-x}\right)=\sum_{k=0}^n \binom{n}{k}f_k

于是得证。

对于 Catalan 数的生成函数 C(x)，[x^n]C(x)^k 有封闭形式

[x^n]C(x)^k = \binom{2n+k}{n}\frac{k}{2n+k}

需要一点转换的套路，设 f(x)=xC(x)，g(x)=x-x^2，不难发现 f(g(x))=x，即 f(x),g(x) 互为复合逆。

那么根据扩展 Lagrange 反演

[x^n]h(f(x))= \frac 1n [x^{n-1}]h'(x) \left( \frac{x}{g(x)}\right)^n

代入 h(x)=x^k，就能得到

[x^n]f(x)^k=\frac kn [x^{n-1}]\frac{x^{k-1}}{(1-x)^n} = \frac kn \binom{2n-k-1}{n-k}

再转换回 C(x) 就是

[x^n]C(x)^k = [x^{n+k}]f(x)^k = \frac{k}{n+k} \binom{2n+k-1}{n} = \frac{k}{n+k} \frac{n+k}{2n+k} \binom{2n+k}{n} = \frac{k}{2n+k}\binom{2n+k}{n}

于是得证。

这个结论还可以推广到任意 广义二项级数，即

\mathcal B_t(x)=\sum_{n=0}^\infty (tn)^{\underline{n-1}} \frac{x^n}{n!}

有

[x^n] \mathcal B_t(x)^k= \binom{tn+k}{n}\frac{k}{tn+k}

可以参见 补档：广义二项级数与指数级数