前置公式
(inom{n}{i}inom{i}{j}=inom{n}{j}inom{n-j}{i-j})
证明考虑组合意义：从 (n) 个里面先选 (i) 个，再从这 (i) 个里面选 (j) 个，等价于先从 (n) 个里面选 (j) 个，再从剩下 (n-j) 个里面选出 (i-j) 个。
形式一
[egin{aligned}
&f(n)=sumlimits_{i=0}^n(-1)^iinom{n}{i}g(i) \
Leftrightarrow &g(n)=sumlimits_{i=0}^n(-1)^iinom{n}{i}f(i)
end{aligned}]
上述两式等价，证明显然。
形式二
[egin{aligned}
&f(n)=sumlimits_{i=0}^n inom{n}{i}g(i) \
Leftrightarrow &g(n)=sumlimits_{i=0}^n(-1)^{n-i}inom{n}{i}f(i)
end{aligned}]
证明：
考虑将二式代入一式。
[egin{aligned}
f(n)&=sumlimits_{i=0}^n inom{n}{i}sumlimits_{j=0}^i(-1)^{i-j}inom{i}{j}f(j)\
&=sumlimits_{i=0}^nsumlimits_{j=0}^i(-1)^{i-j}inom{n}{i}inom{i}{j}f(j)\
&=sumlimits_{i=0}^nsumlimits_{j=0}^i(-1)^{i-j}inom{n}{j}inom{n-j}{i-j}f(j)\
&=sumlimits_{j=0}^n f(j)sumlimits_{i=j}^n(-1)^{i-j}inom{n}{j}inom{n-j}{i-j}\
&=sumlimits_{j=0}^n f(j)sumlimits_{t=0}^{n-j}(-1)^tinom{n}{j}inom{n-j}{t}\
&=sumlimits_{j=0}^n inom{n}{j}f(j)sumlimits_{t=0}^{n-j}inom{n-j}{t}(-1)^t 1^{n-j-t}\
&=sumlimits_{j=0}^ninom{n}{j}f(j)(1-1)^{n-j}
end{aligned}]
- 若 (n ot =j)，则右式值为 (0)；
- 若 (n=j)，则 (0^0) 无意义，考虑直接代入：
[egin{aligned}
&sumlimits_{t=0}^{n-j}inom{n-j}{t}(-1)^t 1^{n-j-t}\
=&inom{0}{0}(-1)^0\
=&1
end{aligned}]
因此，(f(n)=sumlimits_{j=0}^ninom{n}{j}f(j)[j=n]=inom{n}{n}f(n)=f(n))。
证明完毕。
另一表现形式：
[egin{aligned}
&f(n)=sumlimits_{i=m}^n inom{n}{i}g(i) \
Leftrightarrow &g(n)=sumlimits_{i=m}^n(-1)^{n-i}inom{n}{i}f(i)
end{aligned}]
形式三
[egin{aligned}
&f(n)=sumlimits_{i=n}^m inom{i}{n}g(i) \
Leftrightarrow &g(n)=sumlimits_{i=n}^m(-1)^{i-n}inom{i}{n}f(i)
end{aligned}]
这也是最常用的一种形式。
证明：
[egin{aligned}
f(n)&=sumlimits_{i=n}^minom{i}{n}sumlimits_{j=i}^m(-1)^{j-i}inom{j}{i}f(j)\
&=sumlimits_{i=n}^msumlimits_{j=i}^m(-1)^{j-i}inom{j}{i}inom{i}{n}f(j)\
&=sumlimits_{j=n}^m f(j)sumlimits_{i=n}^j(-1)^{j-i}inom{j}{n}inom{j-n}{j-i}\
&=sumlimits_{j=n}^m inom{j}{n}f(j)sumlimits_{t=0}^{n-j}(-1)^tinom{j-n}{t}1^{j-n-t}\
&=sumlimits_{j=n}^m inom{j}{n}f(j)(1-1)^{j-n}\
&=sumlimits_{j=n}^m inom{j}{n}f(j)[j=n]\
&=inom{n}{n}f(n)\
&=f(n)
end{aligned}]
证明完毕。