Pigeonhole and Inclusion-Exclusion - Main Theorem

The Principle of Inclusion-Exclusion is one of the most fundamental results in combinatorics, providing a systematic method for computing the cardinality of unions of finite sets.

Proof by Induction:

We prove by induction on $n$.

Base case: For $n = 1$, the formula gives $|A_1|$, which is trivially true.

For $n = 2$, we need to show $|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|$.

Every element $x$ is counted as follows:

• If $x \in A_1$ only: counted once in $|A_1|$, total = 1 ✓
• If $x \in A_2$ only: counted once in $|A_2|$, total = 1 ✓
• If $x \in A_1 \cap A_2$: counted once in $|A_1|$, once in $|A_2|$, subtracted once in $|A_1 \cap A_2|$, total = $1 + 1 - 1 = 1$ ✓
• If $x \notin A_1 \cup A_2$: not counted, total = 0 ✓

Inductive step: Assume the formula holds for $n-1$ sets. We prove it for $n$ sets.

Note that $A_1 \cup A_2 \cup \cdots \cup A_n = (A_1 \cup \cdots \cup A_{n-1}) \cup A_n$.

By the $n=2$ case: $\left|\bigcup_{i=1}^{n} A_i\right| = \left|\bigcup_{i=1}^{n-1} A_i\right| + |A_n| - \left|\left(\bigcup_{i=1}^{n-1} A_i\right) \cap A_n\right|$

By the inductive hypothesis: $\left|\bigcup_{i=1}^{n-1} A_i\right| = \sum_{k=1}^{n-1} (-1)^{k+1} \sum_{|S|=k, S \subseteq \{1,\ldots,n-1\}} \left|\bigcap_{i \in S} A_i\right|$

Note that $\left(\bigcup_{i=1}^{n-1} A_i\right) \cap A_n = \bigcup_{i=1}^{n-1} (A_i \cap A_n)$.

Applying the inductive hypothesis again: $\left|\bigcup_{i=1}^{n-1} (A_i \cap A_n)\right| = \sum_{k=1}^{n-1} (-1)^{k+1} \sum_{|S|=k, S \subseteq \{1,\ldots,n-1\}} \left|\bigcap_{i \in S} A_i \cap A_n\right|$

Combining these: $\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{k=1}^{n-1} (-1)^{k+1} \sum_{|S|=k, S \subseteq \{1,\ldots,n-1\}} \left|\bigcap_{i \in S} A_i\right| + |A_n| - \sum_{k=1}^{n-1} (-1)^{k+1} \sum_{|S|=k, S \subseteq \{1,\ldots,n-1\}} \left|\bigcap_{i \in S \cup \{n\}} A_i\right|$

Rearranging to group terms by the size of intersection sets, we obtain exactly the formula for $n$ sets. $\square$

Alternative Proof (Direct Counting):

Consider any element $x$ in $\bigcup_{i=1}^n A_i$. Suppose $x$ belongs to exactly $m$ of the sets $A_1, \ldots, A_n$ (where $m \geq 1$).

On the right-hand side, $x$ is counted:

• $\binom{m}{1}$ times in the first sum (single-set terms)
• $-\binom{m}{2}$ times in the second sum (two-set intersections)
• $+\binom{m}{3}$ times in the third sum (three-set intersections)
• And so on...

The net count is: $\sum_{k=1}^{m} (-1)^{k+1} \binom{m}{k} = -\sum_{k=0}^{m} (-1)^k \binom{m}{k} + 1 = -(1-1)^m + 1 = 1$

Therefore, each element in the union is counted exactly once. $\square$