Inclusion-exclusion principle: Visual walkthrough

Before we start, three plain words we will use constantly:

Our goal — the thing we will derive from zero:

$∣ ⋃_{i = 1}^{n} A_{i} ∣ = \sum_{k = 1}^{n} (- 1)^{k + 1} \sum_{1 \leq i_{1} < \dots < i_{k} \leq n} ∣ A_{i_{1}} \cap \dots \cap A_{i_{k}} ∣$

Read out loud that is: the size of the whole blob = (add all singles) − (subtract all pairs) + (add all triples) − …. We will earn every piece of it.

Step 1 — One circle: counting is honest

WHAT. Start with a single set $A$ . We shade it and count the dots inside: that count is $∣ A ∣$ .

WHY. With one set there is no overlap, so nothing is counted twice. This is our baseline of "honest counting" — every dot contributes exactly $1$ . Everything that follows is about repairing this honesty once circles start to overlap.

PICTURE. Look at the blue circle. Each dot is one thing; the bracket labels the total as $∣ A ∣$ .

Here the notation earns its keep: $count of dots in the blue circle ∣ A ∣ = honest, no double-count$

Step 2 — Two circles: the double-count is born

WHAT. Bring in a second set $B$ . The circles overlap. Split the blob into three pieces that never share a dot (mathematicians call such pieces disjoint):

only $A$ , size $a$ (blue-only)
only $B$ , size $b$ (orange-only)
both, size $c = ∣ A \cap B ∣$ (the green lens)

WHY. Disjoint pieces are safe to add — no dot lives in two pieces, so adding their sizes counts every dot once. That gives the true union size honestly: $∣ A \cup B ∣ = blue-only a + orange-only b + lens, both c .$

PICTURE. The lens in the middle is the troublemaker — it belongs to both circles.

Now watch what naive addition does. The full circle $A$ contains blue-only and the lens, so $∣ A ∣ = a + c$ . Likewise $∣ B ∣ = b + c$ . Adding them: $∣ A ∣ + ∣ B ∣ = (a + c) + (b + c) = a + b + the lens counted TWICE 2 c .$ The term $2 c$ is the double-count made visible: the lens got added once from $A$ and once from $B$ .

Step 3 — The fix: subtract the overlap once

WHAT. We have one extra copy of $c$ . Remove exactly one copy by subtracting $∣ A \cap B ∣$ .

WHY. We want every dot counted once. The lens is currently at $2$ ; subtracting $c = ∣ A \cap B ∣$ knocks it down to $1$ , while leaving blue-only and orange-only untouched (they were already at $1$ ).

$∣ A ∣ + ∣ B ∣ - remove one lens copy ∣ A \cap B ∣ = (a + b + 2 c) - c = a + b + c = ∣ A \cup B ∣. ✓$

PICTURE. The red minus-shading cancels one green layer of the lens, leaving it counted once.

Step 4 — Degenerate check: when the circles don't touch

WHAT. Suppose $A$ and $B$ share nothing — no overlap at all. Then the lens is empty: $∣ A \cap B ∣ = 0$ .

WHY. A good formula must survive its edge cases. Plug $0$ into Step 3: $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - 0 = ∣ A ∣ + ∣ B ∣.$ This is exactly "add the disjoint parts" — the additivity rule you already trust. So the general formula contains the simple disjoint rule; it doesn't fight it.

PICTURE. Two separate circles, no lens, nothing to subtract.

Step 5 — Three circles: subtracting too much

WHAT. Add a third set $C$ . Now three lenses form (one per pair) and a tiny center where all three meet. Start honest-ly wrong by adding all singles: $∣ A ∣ + ∣ B ∣ + ∣ C ∣.$

WHY. Track one dot living in the center (all three sets). It got added three times — once by each circle. A dot in exactly two sets got added twice. We now subtract the three pairwise lenses to fix the two-set dots: $- (blue-orange lens ∣ A \cap B ∣ + blue-green lens ∣ A \cap C ∣ + orange-green lens ∣ B \cap C ∣) .$

PICTURE. Every pairwise lens gets one red subtraction. Follow the center dot: it lives in all three lenses, so it gets subtracted three times.

Tally for the center dot so far: $from 3 singles + 3 from 3 pairs - 3 = 0.$ Disaster: the all-three dots have vanished from the count entirely.

Step 6 — Add the center back

WHAT. Restore the vanished center by adding the triple intersection once: $+ the tiny center region ∣ A \cap B \cap C ∣ .$

WHY. The center dot sat at $0$ after Step 5; we want it at $1$ . Adding it once lifts $0 \to 1$ . Meanwhile the two-set dots (already correct at $1$ ) are not in the triple region, so they are untouched.

PICTURE. Green plus-shading fills the center back in — every region now sits at exactly $1$ .

The rhythm has appeared: +singles, −pairs, +triples. Add-subtract-add. The signs alternate, and the picture just told us why: each layer of subtraction over-corrects the deepest dots, forcing the next layer to flip sign.

Step 7 — Why the signs must alternate (the counting bar chart)

WHAT. Take a dot living in exactly $m$ of the sets. Count how many terms of each type contain it.

WHY. A dot in $m$ sets appears in:

$(1 m)$ single terms (choose 1 of its $m$ sets),
$(2 m)$ pair terms (choose 2 of its $m$ sets),
… $(k m)$ of the $k$ -fold intersections.

The symbol $(k m)$ (a binomial coefficient, see Counting Principles & Combinatorics) means "number of ways to pick $k$ things out of $m$ ." Its net contribution, with alternating signs, is: $S = (1 m) - (2 m) + (3 m) - \dots = \sum_{k = 1}^{m} (- 1)^{k + 1} (k m) .$

PICTURE. A bar chart of the terms $+ (1 m), - (2 m), + (3 m), \dots$ for $m = 4$ : the positive and negative bars almost cancel, leaving a leftover of exactly $1$ .

Why exactly $1$ ? The Binomial Theorem with $x = - 1$ says all $m + 1$ signed terms (including $k = 0$ ) sum to zero: $\sum_{k = 0}^{m} (- 1)^{k} (k m) = (1 - 1)^{m} = 0.$ Peel off the $k = 0$ term, $(0 m) = 1$ : $0 = k = 0 1 - our alternating sum S \Rightarrow S = 1.$ Every dot, no matter how many sets it lives in, is counted exactly once. That is the whole theorem, and the alternating signs are forced — not chosen.

Step 8 — Edge case: a dot in zero sets

WHAT. What about a dot outside every circle ( $m = 0$ )?

WHY. It appears in no single, no pair, no intersection — its net contribution is $0$ . Good: the union should count only dots inside at least one circle, and this dot is inside none. The formula silently ignores it, exactly as it should. (No figure needed — the empty tally is the picture.)

The one-picture summary

The whole derivation is one sentence made of shaded regions: add each circle, peel off each pairwise lens, paint the triple center back, and every deeper layer flips sign — until each region sits at height exactly $1$ .

Recall Feynman retelling — the whole walkthrough in plain words

Picture three overlapping hula-hoops on the floor with beads scattered under them. First you count the beads under each hoop separately and add — but beads under two hoops got counted twice, and beads under all three got counted three times. So you go around and subtract every pair-overlap once. That fixes the two-hoop beads perfectly. But the beads dead-center — under all three — you just subtracted three times after adding three times, so they've dropped to zero, gone! You march back and add the center beads once more. Now everyone is counted exactly one time. If you had four hoops, subtracting the four-way overlaps would over-fix again, so you'd subtract the deepest layer, and so on: add, subtract, add, subtract, switching signs each round. The reason it always lands on exactly one per bead is a tidy algebra fact — the plus and minus counts of "how many overlaps a bead sits in" nearly cancel, leaving a clean leftover of $1$ .

Active recall

Trace-the-lens :: The lens is the only region inside both circles, so $∣ A ∣$ and $∣ B ∣$ each count it once → total twice. Center dot height after pairs :: It sits at $+ 3 - 3 = 0$ , i.e. erased — wrong, we want $1$ , so we add the triple back. Why leftover is 1 :: Because $\sum_{k = 0}^{m} (- 1)^{k} (k m) = 0$ and the $k = 0$ term is $1$ , forcing the $k \geq 1$ alternating sum $S = 1$ .

Connections

Parent: Inclusion–Exclusion Principle — the full statement and proofs
Set Theory & Venn Diagrams — the circles, unions, and lenses drawn here
Counting Principles & Combinatorics — the meaning of $(k m)$ used in Step 7
Binomial Theorem — the $(1 - 1)^{m} = 0$ identity that forces the signs
Probability Axioms — the disjoint case of Step 4
Derangements & Permutations — where this walkthrough pays off
Bonferroni Inequalities — what happens if you stop the alternating sum early