主要形式

形式一

$$f(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}f(i)$$

形式二

$$f(n)=\sum\limits_{i=0}^n\dbinom{n}{i}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}f(i)$$

形式三

$$f(n)=\sum\limits_{i=n}^m(-1)^i\dbinom{i}{n}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=n}^m(-1)^{i}\dbinom{i}{n}f(i)$$

形式四

$$f(n)=\sum\limits_{i=n}^m\dbinom{i}{n}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=n}^m(-1)^{i-n}\dbinom{i}{n}f(i)$$

证明

反演基本形式如下

$$f(n) = \sum\limits_{i=0}^n{a_i}g(i)$$

$$g(n) = \sum\limits_{i=0}^n{b_i}f(i)$$

在形式一中，有 $a_i = b_i = (-1)^i\dbinom{n}{i}$

要证

$$f(n)=\sum\limits_{i=0}^na_ig(i)\Longrightarrow g(n)=\sum\limits_{i=0}^nb_if(i)$$

只要证

$$g(n)=\sum\limits_{i=0}^nb_if(i)=\sum\limits_{i=0}^nb_i\sum\limits_{j=0}^ia_jg(j) = \sum\limits_{j=0}^ng(j)\sum\limits_{i=j}^nb_ia_j$$

只要证

$$\sum\limits_{i=j}^nb_ia_j=[j=n]$$

只要证

$$\sum\limits_{i=j}^n(-1)^i\dbinom{n}{i}\times(-1)^j\dbinom{i}{j}=[j=n]$$

引理: $\dbinom{n}{i}\dbinom{i}{j}=\dbinom{n}{j}\dbinom{n-j}{n-i}$

证明: 考虑组合意义，$n$ 个数中选 $i$ 个数，再从中选 $j$ 个数的方案数。等价于 $n$ 个数中先选出 $j$ 个数，再从剩下 $n-j$ 个数中选出 $i-j$ 个数的方案数

$\dbinom{n}{i}\dbinom{i}{j}=\dbinom{n}{j}\dbinom{n-j}{i-j}=\dbinom{n}{j}\dbinom{n-j}{n-i}$

$$\begin{aligned} &\sum\limits_{i=j}^n(-1)^i\dbinom{n}{i}\times(-1)^j\dbinom{i}{j}\\
=&\sum\limits_{i=j}^n(-1)^{i}(-1)^j\dbinom{n}{j}\dbinom{n-j}{n-i}\\
=&\dbinom{n}{j}(-1)^j\sum\limits_{i=0}^{n-j}{(-1)}^{i+j}\dbinom{n-j}{i}\\
=&\dbinom{n}{j}(1-1)^{n-j}\\
=&[j=n] \end{aligned} $$

反之亦然，二项式反演得证

（感觉还是 vfk 课件上的推导更加自然