Inclusion-exclusion principle

WHY does this principle exist?

WHAT goes wrong with naive addition: an element in $k$ of the sets is added $k$ times when we want it added $1$ time. We need a correction that nets to $1$ for every $k \ge 1$.

Deriving the two-set case from scratch

WHY start here: every general case is built from this.

Partition the union $A \cup B$ into three disjoint pieces:

• only $A$ (not $B$): size $a$
• only $B$ (not $A$): size $b$
• both $A$ and $B$: size $c = |A \cap B|$

Then by disjoint addition: $|A \cup B| = a + b + c.$ But $|A| = a + c$ and $|B| = b + c$. So: $|A| + |B| = (a+c) + (b+c) = a + b + 2c.$ Why this step? The overlap $c$ appears in both $|A|$ and $|B|$, hence twice. Subtract one copy of $c = |A\cap B|$: $|A| + |B| - |A\cap B| = a + b + c = |A\cup B|. \checkmark$

Three sets — derive, don't memorise

Start by adding singles, then we over-subtract the pairwise overlaps and must add the triple back.

$|A| + |B| + |C| \quad\text{counts a triple-element 3 times.}$ Subtract the three pairwise intersections: $-(|A\cap B| + |A\cap C| + |B\cap C|).$ Why this step? Each pairwise term removes the double-counting of elements in exactly two sets — good. But an element in all three sets sat in all three pairwise intersections, so it just got subtracted $3$ times after being added $3$ times → net $0$. That's wrong; we want it counted once.

So add back the triple intersection once: $+|A\cap B\cap C|.$

The general formula (and WHY the signs alternate)

HOW the alternating signs are forced — first-principles proof. Take any element $x$ lying in exactly $m$ of the sets ($m \ge 1$). We must show the right-hand side counts it exactly once.

• $x$ appears in $\binom{m}{1}$ single terms, $\binom{m}{2}$ pair terms, …, $\binom{m}{k}$ of the $k$-fold intersections.
• Its net contribution is: $S \;=\; \sum_{k=1}^{m} (-1)^{k+1}\binom{m}{k}.$ Use the binomial theorem with $x=-1$: $\sum_{k=0}^{m}(-1)^{k}\binom{m}{k} = (1-1)^m = 0.$ Why this step? This single identity contains all our terms, including the $k=0$ term $\binom{m}{0}=1$. Split off $k=0$: $0 \;=\; \binom{m}{0} + \sum_{k=1}^{m}(-1)^{k}\binom{m}{k} \;=\; 1 - \sum_{k=1}^{m}(-1)^{k+1}\binom{m}{k} \;=\; 1 - S.$ Why the sign flip? For $k\ge 1$, $(-1)^k = -(-1)^{k+1}$, so $\sum_{k=1}^m(-1)^k\binom mk = -S$. Hence $0 = 1 - S$, giving $S = 1.$ Every element is counted exactly once — QED.

Probability version

Worked examples

Common mistakes

Active recall

Connections

• Set Theory & Venn Diagrams — the union/intersection structure underlying the principle
• Counting Principles & Combinatorics — uses $\binom nk$ in the general proof
• Probability Axioms — the additivity axiom is the disjoint special case
• Derangements & Permutations — a classic application
• Binomial Theorem — provides the $(1-1)^m=0$ identity that proves alternating signs
• Bonferroni Inequalities — truncating I–E gives upper/lower bounds

Concept Map

Hinglish (regional understanding)