二项式反演

问题

有数列 ，对于每一个数字 有

求证，有 。

引理

考虑当 时， 的值。

当 为奇数时： 当 为偶数时：

移项可得

证明

考虑使用数学归纳法。

当 时，。

显然 。

现在假设，对于 ，都满足条件，现在来证明 时满足条件。 我们来看 的组合意义。

我们可以理解成，一个班级共有 个人，我们要先选出 个人当班干部，这 个人中再选出 个人当组长，剩余的 个人当副组长。

那我们就可以看成，先从 个人选出 个人当组长，再从剩下的 个人中，选 个人当副组长（ 人是平民）。

也就是说，。 证完力！