Past exam of the mathematics course of the University of Cambridge / 2009 / ia / Paper 4 / 6E / a / Solution

For finite sets $X_1,\dots ,X_N$, the inclusion-exclusion principle statesTo prove it, fix an element belonging to exactly $s\ge 1$ of these sets. At level $r$ it is counted in precisely $\left(\genfrac{}{}{0ex}{}{s}{r}\right)$ intersections, so its total multiplicity on the right isby 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.