二项式反演的证明

设 $f_n$ 表示恰好用 $n$ 个物品的方案数，$g_n$ 表示 $n$ 个物品任意选的方案数。

如果我们知道 $f$ 求 $g$，显然 $g_n=\sum_{i=0}^n\binom{n}{i}f_i$ 但通常 $g$ 是好求的，$f$ 不好求，此时就可以使用二项式反演求出 $f$： $f_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g_i$

我们先证明以下两个引理： $1.\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}=[n=0]$ $2.\binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k}$

证明完引理后，我们开始正式证明：

考虑从结论出发 $\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g_i$ $=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}\sum_{j=0}^i\binom{i}{j}f_j$ $=\sum_{i=0}^n\sum_{j=0}^i(-1)^{n-i}\binom{n}{i}\binom{i}{j}f_j$ $=\sum_{j=0}^n\sum_{i=j}^n(-1)^{n-i}\binom{n}{i}\binom{i}{j}f_j$ $=\sum_{j=0}^n\sum_{i=j}^n(-1)^{n-i}\binom{n}{j}\binom{n-j}{i-j}f_j$ $=\sum_{j=0}^n\binom{n}{j}f_j\sum_{i=j}^n(-1)^{n-i}\binom{n-j}{i-j}$ 推不下去了，考虑换元 $k=i-j$，即 $i=j+k$。 $=\sum_{j=0}^n\binom{n}{j}f_j\sum_{k=0}^{n-j}(-1)^{n-(j+k)}\binom{n-j}{k}$ $=\sum_{j=0}^n\binom{n}{j}f_j\sum_{k=0}^{n-j}(-1)^{(n-j)-k}\binom{n-j}{k}$ $=\sum_{j=0}^n\binom{n}{j}f_j[n-j=0]$ $=\binom{n}{n}f_n$ $=f_n$ $Q.E.D.$