$$
g(n) =\sum_{i=1}^n{n\choose i}f(i) \Longleftrightarrow f(n)=\sum_{i=1}^n (-1)^{n-i}{n \choose i}g(i)
$$

先把左边代入右边消掉

$$
f(n)=\sum_{i=1}^{n}(-1)^{n-i}{n\choose i}*\sum_{j=1}^{i}{i\choose j}f(j)
$$

换一下式子的顺序

$$
f(n)=\sum_{j=1}^{n}f(j)*\sum_{i=j}^{n}(-1)^{n-i}{n\choose i}{i\choose j}
$$

拆开组合数并化简

$$
\sum_{i=j}^{n}(-1)^{n-i}\cfrac{n!}{i!(n-i)!}\cfrac{i!}{j!(i-j)!}
$$

$$
=\sum_{i=j}^{n}(-1)^{n-i}\cfrac{n!}{j!(n-i)!(i-j)!}
$$

$$
=\cfrac{n!}{j!}\sum_{i=j}^{n}\cfrac{(-1)^{n-i}}{(n-i)!(i-j)!}
$$

内乘外除$(n-j)!$

$$
=\cfrac{n!}{j!(n-j)!}\sum_{i=j}^{n}(-1)^{n-i}\cfrac{(n-j)!}{(n-i)!(i-j)!}
$$

把分数转回组合数

$$
={n\choose j}\sum_{i=j}^{n}(-1)^{n-i}{n-j\choose n-i}
$$

因为

$$
f(n)=\sum_{j=1}^{n}[j==n]*f(j)
$$

所以就相当于证明：

$$
{n\choose j}\sum_{i=j}^{n}(-1)^{n-i}{n-j\choose n-i}=\begin{cases}

0\quad(j<n)\

1\quad(j=n) \

\end{cases}
$$

证明：

  • $j=n$ 时：

    原式等于：

$$
{n\choose n}(-1)^0{0\choose0}=1
$$

  • $j\not = n$ 时：

    有$\sum_{i=j}^{n}(-1)^{n-i}{n-j\choose n-i}=0$

    证明：

    当 $n-j$ 为奇数时，

    取值正好有 $n-j+1$ 个，且正好两两相反可以抵消，也就是 ${n-j\choose n-i}$ 和 ${n-j\choose n-j-(n-i)}$，他们值相等，但系数相反；

    当 $n-j$ 为偶数时，

    根据二项式定理：

$$
\sum_{i=0}^n C(n,i) (-1)^{n-i}
$$

$$
= \sum_{i=0}^n C(n,i) (-1)^{n-i}1^i
$$

$$
=(1-1)^n
$$

$$
=0^n
$$

$$
=0
$$

反演得证