省选-数学-二项式反演

基础形式

若对所有 $n\ge 0$：

$$f(n) = \sum_{k=0}^n \binom{n}{k}\, g(k)$$

则一定有：

$$g(n) = \sum_{k=0}^n (-1)^{n-k}\, \binom{n}{k}\, f(k)$$

证明

普通形式

直接带入：

$$\sum_{k=0}^n (-1)^{n-k}\binom{n}{k} \sum_{t=0}^k \binom{k}{t} g(t)$$ $$\sum_{t=0}^n g(t) \sum_{k=t}^n (-1)^{n-k} \binom{n}{k}\binom{k}{t}$$

利用组合恒等式 $\dbinom{n}{k}\dbinom{k}{t} = \dbinom{n}{t}\dbinom{n-t}{k-t}$：

$$\sum_{t=0}^n g(t)\binom{n}{t} \sum_{k=t}^n (-1)^{n-k} \binom{n-t}{k-t}$$

令 $m = k-t$，$s = n-t$：

$$\sum_{m=0}^{s} (-1)^{s-m}\binom{s}{m} = (1-1)^s$$

然后之后 $n=t$ 的时候不为 $0$，所以证毕。