[proofplan]
We prove the identity by tracking the contribution of a single element to the right-hand side. For an element $x$ in the union, let $m$ be the number of [sets](/page/Set) among $S_1,\ldots,S_n$ that contain $x$. The $r$-fold intersections containing $x$ are exactly the choices of $r$ sets from those $m$ sets, so the total coefficient of $x$ is an alternating binomial sum. The [Binomial Theorem](/theorems/750) evaluates this coefficient as $1$, while elements outside the union contribute $0$.
[/proofplan]
[step:Define the membership set of a fixed element]
Let $U := \bigcup_{i=1}^{n} S_i$. Since each $S_i$ is finite and there are finitely many indices, $U$ is finite. Fix $x \in U$, and define the index set
\begin{align*}
A_x := \{i \in \{1,\ldots,n\} : x \in S_i\}.
\end{align*}
Because $x \in U$, the set $A_x$ is nonempty. Let $m := |A_x|$, so $1 \le m \le n$.
[guided]
Let
\begin{align*}
U := \bigcup_{i=1}^{n} S_i
\end{align*}
denote the finite union appearing on the left-hand side. The hypothesis that $S_1,\ldots,S_n$ are finite sets ensures that $U$ is finite, so it makes sense to prove the cardinality identity by counting how many times each element of $U$ appears on the right-hand side.
Fix an element $x \in U$. We record exactly which of the sets contain $x$ by defining
\begin{align*}
A_x := \{i \in \{1,\ldots,n\} : x \in S_i\}.
\end{align*}
This is a finite subset of $\{1,\ldots,n\}$. Since $x \in U$, there exists at least one index $i$ with $x \in S_i$, so $A_x$ is nonempty. Define
\begin{align*}
m := |A_x|.
\end{align*}
Thus $m$ is the number of sets among $S_1,\ldots,S_n$ that contain $x$, and it satisfies $1 \le m \le n$.
[/guided]
[/step]
[step:Count the intersections in which the fixed element appears]
For a fixed integer $r$ with $1 \le r \le n$, the element $x$ belongs to an intersection
\begin{align*}
S_{i_1} \cap \cdots \cap S_{i_r},
\qquad
1 \le i_1 < \cdots < i_r \le n,
\end{align*}
if and only if $\{i_1,\ldots,i_r\} \subseteq A_x$. Hence the number of $r$-fold intersections containing $x$ is
\begin{align*}
\binom{m}{r}
\end{align*}
when $1 \le r \le m$, and is $0$ when $r > m$.
[guided]
Fix an integer $r$ with $1 \le r \le n$. An $r$-fold intersection on the right-hand side has the form
\begin{align*}
S_{i_1} \cap \cdots \cap S_{i_r},
\qquad
1 \le i_1 < \cdots < i_r \le n.
\end{align*}
The element $x$ lies in this intersection exactly when $x$ lies in each of the sets $S_{i_1},\ldots,S_{i_r}$. By the definition of $A_x$, this condition is equivalent to
\begin{align*}
\{i_1,\ldots,i_r\} \subseteq A_x.
\end{align*}
Thus counting the $r$-fold intersections containing $x$ is the same as counting the $r$-element subsets of the $m$-element set $A_x$. There are
\begin{align*}
\binom{m}{r}
\end{align*}
such subsets when $1 \le r \le m$. If $r > m$, there is no $r$-element subset of $A_x$, so the number of such intersections is $0$.
[/guided]
[/step]
[step:Evaluate the alternating coefficient of the fixed element]
The total coefficient with which $x$ is counted on the right-hand side is therefore
\begin{align*}
\sum_{r=1}^{m} (-1)^{r+1}\binom{m}{r}.
\end{align*}
Using $\binom{m}{0}=1$, we rewrite this as
\begin{align*}
\sum_{r=1}^{m} (-1)^{r+1}\binom{m}{r}
&= -\sum_{r=1}^{m} (-1)^r \binom{m}{r} \\
&= -\left(\sum_{r=0}^{m} (-1)^r \binom{m}{r} - \binom{m}{0}\right).
\end{align*}
By the [Binomial Theorem](/theorems/750) applied with $a=1$ and $b=-1$,
\begin{align*}
\sum_{r=0}^{m} \binom{m}{r}1^{m-r}(-1)^r
= (1+(-1))^m
= 0^m
= 0,
\end{align*}
because $m \ge 1$. Therefore
\begin{align*}
\sum_{r=1}^{m} (-1)^{r+1}\binom{m}{r}
= -(0-1)
= 1.
\end{align*}
[guided]
From the previous step, for each $r$ with $1 \le r \le m$, the element $x$ appears in exactly $\binom{m}{r}$ of the $r$-fold intersections. Each such $r$-fold intersection is counted with coefficient $(-1)^{r+1}$ in the formula. Therefore the total coefficient of $x$ on the right-hand side is
\begin{align*}
\sum_{r=1}^{m} (-1)^{r+1}\binom{m}{r}.
\end{align*}
We evaluate this alternating sum by relating it to the full binomial expansion of $(1-1)^m$. Since $\binom{m}{0}=1$, we have
\begin{align*}
\sum_{r=1}^{m} (-1)^{r+1}\binom{m}{r}
&= -\sum_{r=1}^{m} (-1)^r \binom{m}{r} \\
&= -\left(\sum_{r=0}^{m} (-1)^r \binom{m}{r} - \binom{m}{0}\right).
\end{align*}
We now apply the [Binomial Theorem](/theorems/750) to the integer $m \ge 1$ with $a=1$ and $b=-1$. It gives
\begin{align*}
\sum_{r=0}^{m} \binom{m}{r}1^{m-r}(-1)^r
= (1+(-1))^m
= 0^m
= 0.
\end{align*}
Since $m \ge 1$, the expression $0^m$ equals $0$. Substituting this value into the previous identity gives
\begin{align*}
\sum_{r=1}^{m} (-1)^{r+1}\binom{m}{r}
= -(0-1)
= 1.
\end{align*}
Thus every element $x \in U$ contributes exactly one unit to the right-hand side.
[/guided]
[/step]
[step:Sum the elementwise contributions to obtain the formula]
Every element $x \in U$ contributes exactly $1$ to the right-hand side by the previous step. If $x \notin U$, then $x$ belongs to none of the sets $S_i$ and hence belongs to no intersection appearing on the right-hand side, so its contribution is $0$. Since all sets involved are finite, summing these elementwise contributions gives
\begin{align*}
\left|\bigcup_{i=1}^{n} S_i\right|
=
\sum_{r=1}^{n} (-1)^{r+1}
\sum_{1 \le i_1 < \cdots < i_r \le n}
|S_{i_1} \cap \cdots \cap S_{i_r}|.
\end{align*}
This is the desired inclusion-exclusion formula.
[/step]
