# Equation for cardinality of the union of $n$ sets

Let $A_1,\dots,A_n$ be finite sets.

I want to show the following equation.

$\lvert A_1 \cup \dots \cup A_n \rvert = \displaystyle\sum_{k=1}^n{(-1)^{k+1}\left( \displaystyle\sum_{1 \leq i_1 \lt \dots \lt i_k \leq n} {\lvert A_{i_1} \cap \dots \cap A_{i_k} \rvert} \right)}$

I want to proof it by induction and I think might be useful that

$\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$

for finite sets $A$, $B$.

I don't get any further when I try to write down the induction step.

• For the induction write $$A_1 \cup ... \cup A_{n-1} \cup A_n \cup A_{n+1} = A_1 \cup ... \cup A_{n-1} \cup B$$ where $B = A_n \cup A_{n+1}$ That gives you the union of $n$ sets against which you can apply your hypothesis. – Scott Burns Dec 1 '16 at 0:12

You’re quite right that the two-set case is used in the induction step, but it’s still a little tricky to work through.

Suppose that you know it for $n$. Let $B=A_1\cup\ldots\cup A_n$. Then

\begin{align*} |A_1\cup\ldots\cup A_{n+1}|&=|B\cup A_{n+1}|\\ &=|B|+|A_{n+1}|-|B\cap A_{n+1}|\\ &=\sum_{k=1}^n(-1)^{k+1}\left(\sum_{1\le i_1<\ldots<i_k\le n}|A_{i_1}\cap\ldots\cap A_{i_k}|\right)+|A_{n+1}|-|B\cap A_{n+1}|\;.\tag{1} \end{align*}

Now

\begin{align*} |A_{n+1}|-|B\cap A_{n+1}|&=|A_{n+1}|-\left|\left(\bigcup_{k=1}^nA_k\right)\cap A_{n+1}\right|\\ &=|A_{n+1}|-\left|\bigcup_{k=1}^n(A_k\cap A_{n+1})\right|\\ &=|A_{n+1}|-\sum_{k=1}^n(-1)^{k+1}\left(\sum_{1\le i_1<\ldots<i_k\le n}|(A_{i_1}\cap A_{n+1})\cap\ldots\cap(A_{i_k}\cap A_{n+1})|\right)\\ &=|A_{n+1}|+\sum_{k=1}^n(-1)^{k+2}\left(\sum_{1\le i_1<\ldots<i_k\le n}|A_{i_1}\cap\ldots\cap A_{i_k}\cap A_{n+1}|\right)\\ &=\sum_{k=1}^{n+1}(-1)^{k+1}\left(\sum_{1\le i_1<\ldots<i_{k-1}\le n<i_k=n+1}|A_{i_1}\cap\ldots\cap A_{i_k}|\right)\tag{2} \end{align*}

by the induction hypothesis applied to the $n$ sets $A_1\cap A_{n+1},\ldots,A_n\cap A_{n+1}$.

To see what’s really going on here, it’s helpful to realize that the sum $(2)$ covers all of the intersections of $A_i$s that include the new $A_{n+1}$, while the first term of $(1)$ covers the ones that don’t include $A_{n+1}$. Combining results, we now have

\begin{align*} \left|\,\bigcup_{k=1}^{n+1}A_k\,\right|&=\sum_{k=1}^n(-1)^{k+1}\left(\sum_{1\le i_1<\ldots<i_k\le n}|A_{i_1}\cap\ldots\cap A_{i_k}|\right)\\ &\qquad+\sum_{k=1}^{n+1}(-1)^{k+1}\left(\sum_{1\le i_1<\ldots<i_{k-1}\le n<i_k=n+1}|A_{i_1}\cap\ldots\cap A_{i_k}|\right)\\ &=\sum_{k=1}^{n+1}(-1)^{k+1}\left(\sum_{1\le i_1<\ldots<i_k\le n+1}|A_{i_1}\cap\ldots\cap A_{i_k}|\right)\;, \end{align*}

as desired.