\[f(n)=\sum_{i=0}^{n} \binom{n}{i} g(i) \Leftrightarrow g(n)=\sum_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)
\]
以下是本人的证明，是直接证明。
前置证明：\(\binom{r}{m}\binom{m}{k}=\binom{r}{k}\binom{r-k}{m-k}\),这个简单划一下就行了。
\[\begin{align}
f(n) &=\sum_{i=0}^{n} \binom{n}{i} g(i)\&= \sum_{i=0}^{n} \binom{n}{i} \sum_{j=0}^{i} (-1)^{i-j} \binom{i}{j} f(j)\&= \sum_{j=0}^{n} f(j) \sum_{i=j}^{n} (-1)^{i-j} \binom{n}{i} \binom{i}{j} \\end{align}
\]
到这一步，当\(j=n\)时，\(\sum_{i=j}^{n} (-1)^{i-j} \binom{n}{i} \binom{i}{j} = (-1)^0 \binom{n}{n} \binom{n}{n} = 1\)。则这一项与左式的\(f(n)\)对消，即剩余的值为0。则我们考虑\(j < n\)的情况。观察式子，我们必须要求每个\(f(j)\)的系数均为0才行。即证\(\forall j<n , \sum_{i=j}^{n} (-1)^{i-j} \binom{n}{j} \binom{n-j}{i-j} =0\)。
\[\begin{align}
\sum_{i=j}^{n} (-1)^{i-j} \binom{n}{j} \binom{n-j}{i-j} =0
&= \binom{n}{j} \sum_{i=j}^{n} (-1)^{i-j} \binom{n-j}{i-j} \&= \binom{n}{j} \sum_{i=0}^{n-j} (-1)^i \binom{n-j}{i} \&= \binom{n}{j} (-1+1)^{n-j} \&= 0
\end{align}
\]
由于是等式，所以从左到右正确即从右到左正确。证毕。
二项式反演的另一种表现形式
\[f(n)=\sum_{i=0}^{n} (-1)^i \binom{n}{i} g(i) \Leftrightarrow g(n)=\sum_{i=0}^{n} (-1)^i \binom{n}{i} f(i)
\]
还是同理的证明。
\[\begin{align}
f(n) &=\sum_{i=0}^{n} (-1)^i \binom{n}{i} g(i)\&= \sum_{i=0}^{n} (-1)^i \binom{n}{i} \sum_{j=0}^{i} (-1)^j \binom{i}{j} f(j)\&= \sum_{j=0}^{n} f(j) \sum_{i=j}^{n} (-1)^{i+j} \binom{n}{i} \binom{i}{j} \\end{align}
\]
这个和上面的一个式子完全相同。-1的系数一个是i-j一个是i+j，一样的。
或者说，既然我们证明了第一种表现形式，那么我们可以把第二种式子当中的\(g(i)\)看成是第一种的\((-1)^i g(i)\)，那么就直接算完了。
二项式反演证明
原文：https://www.cnblogs.com/surculosaoi/p/12669054.html
