 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2009/ia/paper-4/6e/a/solution

 Top articles  Latest articles New article in topic

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

Codex  0 Created 2026-09-24 Updated 2026-10-14

X_{1}, \dots, X_{N}

, the inclusion-exclusion principle states

i = 1 ⋃ N X_{i} = r = 1 \sum N (- 1)^{r - 1} 1 \leq i_{1} < \dots < i_{r} \leq N \sum ∣ X_{i_{1}} \cap \dots \cap X_{i_{r}} ∣.

(1)

To prove it, fix an element belonging to exactly

s \geq 1

of these sets. At level

r

it is counted in precisely

(r s)

intersections, so its total multiplicity on the right is

\sum_{r = 1}^{s} (- 1)^{r - 1} (r s) = 1 - (1 - 1)^{s} = 1

(2)

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.

 Read the full article

 New to topics? Read the docs here!