## 2021.03.13 OI Wiki-普通生成函数

请求出下列数列的普通生成函数（形式幂级数形式和封闭形式）。

$a_n=\binom{m+n}{n}$（$m$ 是常数，$n\ge0$）。

形式幂级数形式：$\sum_{n\ge 0}\binom{m+n}{n}x^n$。

封闭形式：$\dfrac{1}{(1-x)^{m+1}}$。

结论 $1$：$C_{m+n}^{n}=C_{m+n-1}^{n}+C_{m+n-1}^{n-1}$。

证明 $1$：杨辉三角基本性质。

结论 $2$：$\sum_{i=0}^{n}C_{m+i-1}^{i}=C_{m+n}^{n}$（$m\ge1$）。

证明 $2$：$n=0$ 时显然相等。

假设 $n-1$ 时相等，则 $n$ 时：

$LHS=\sum_{i=0}^{n}C_{m+i-1}^{i}$

$=\sum_{i=0}^{n-1}C_{m+i-1}^{i}+C_{m+n-1}^{n}$

$=\sum_{i=0}^{n-1}C_{m+i-1}^{i}+C_{m+n}^{n}-C_{m+n-1}^{n-1}$

$=C_{m+n}^{n}=RHS$

因此左右两式相等。

回到原题，我们要证 $\sum_{n\ge 0}\binom{m+n}{n}x^n=\dfrac{1}{(1-x)^{m+1}}$。

$m=0$ 时显然相等。

假设 $m-1$ 时相等，则 $m$ 时：

$RHS=\dfrac{1}{(1-x)^{m+1}}$

$=\dfrac{1}{(1-x)^{m}}\times\dfrac{1}{1-x}$

$=\sum_{n\ge 0}\binom{m-1+n}{n}x^n\sum_{n\ge 0}x^n$

$=\sum_{n\ge 0}x^n\sum_{i=0}^{n}\binom{m-1+i}{i}$

$=\sum_{n\ge 0}x^nC_{m+n}^{n}=LHS$

因此原数列的普通生成函数的封闭形式为 $\dfrac{1}{(1-x)^{m+1}}$。

## 2021.02.18 P4821 [中山市选]生成树
结论：$\sum_{i=0}^{n}C_{n}^{i}\times a^{n-i}\times(n-i)=a\times n\times(a+1)^{n-1}$。

证明：注意到两边都是关于 $a$ 的 $n$ 次多项式，我们只需证明它们系数对应相等即可。

考虑 $a^k(0\le k\le n)$ 在左右两式的系数：

左式：$C_{n}^{n-k}\times k=\dfrac{n!}{(n-k)!\times k!}\times k=\dfrac{n!}{(n-k)!\times (k-1)!}$。

右式：$C_{n-1}^{k-1}\times n=\dfrac{(n-1)!}{(n-k)!\times k!}\times n=\dfrac{n!}{(n-k)!\times (k-1)!}$。

因此左右两式相等。