一般容斥原理

固定任意一个元素 $x$。若 $x$ 不属于 $A_1,\ldots,A_n$ 中的任何一个,它对两边的贡献都是 $0$,因此设 $x$ 恰好属于 $m\ge 1$ 个集合。

对每个 $k$,包含 $x$ 的 $k$ 重交集 $A_{i_1}\cap\cdots\cap A_{i_k}$ 的个数等于从含 $x$ 的 $m$ 个集合中选出 $k$ 个的方法数,即 $\binom{m}{k}$。因此 $x$ 对右边的总贡献为 $\sum_{k=1}^n(-1)^{k+1}\binom{m}{k}=\sum_{k=1}^m(-1)^{k+1}\binom{m}{k}$($k>m$ 的项因 $\binom{m}{k}=0$ 而消失)。

由二项定理,$\sum_{k=0}^m(-1)^k\binom{m}{k}=(1-1)^m=0$,于是 $\sum_{k=1}^m(-1)^k\binom{m}{k}=-1$,乘以 $-1$ 恰好得到 $\sum_{k=1}^m(-1)^{k+1}\binom{m}{k}=1$。

因此至少属于一个集合的每个元素对右边的贡献恰为 $1$,与它对 $\left|\bigcup_{i=1}^n A_i\right|$ 的贡献 $1$ 相符;不属于任何集合的元素对两边的贡献都是 $0$。由于每个元素对两边的贡献相同,两边相等。