= Solution
For finite sets $X_1,\ldots,X_N$, the <inclusion-exclusion principle> states
$$
\boxed{\left|\bigcup_{i=1}^NX_i\right|=\sum_{r=1}^N(-1)^{r-1}\sum_{1\leq i_1<\cdots<i_r\leq N}|X_{i_1}\cap\cdots\cap X_{i_r}|.}
$$
To prove it, fix an element belonging to exactly $s\geq1$ of these sets. At level $r$ it is counted in precisely $\binom sr$ intersections, so its total multiplicity on the right is
$$
\sum_{r=1}^s(-1)^{r-1}\binom sr=1-(1-1)^s=1
$$
by the <binomial theorem>. An element in no set contributes zero. Summing these equal multiplicities over the finite union proves <inclusion-exclusion>. This also explains why pairwise subtraction alone is insufficient: elements in triple and higher intersections must receive the alternating corrections.
Back to article page
