%% ================================================================
\newpage
\section{A proof of the inclusion-exclusion formula}

\begin{prop*}[\bfidx{Inclusion-exclusion formula}]
Let $A_1, \ldots, A_n$ be events.  Then
$$
	P(\cup_{i=1}^n A_i) =
		\sum_{1 \le i \le n} P(A_i)
		- \sum_{1 \le i < j \le n} P(A_i \cap A_j)
		+ \sum_{1 \le i < j < k \le n} P(A_i \cap A_j \cap A_k)
		- \ldots
		+ (-1)^{n+1} P(A_1 \cap \ldots \cap A_n).
$$
\begin{proof}
The proof is by strong induction.  For the base case $n=1$, the left-hand side is
$P(A)$ and the right-hand side is also $P(A)$.

\begin{center}* * *\end{center}

A bonus case, $n=2$, is not necessary but helps to illustrate what's going on.
The formula is
$$
	P(A \cup B) = P(A) + P(B) - P(A \cap B).
$$
This is easy to prove using Venn diagrams and finite additivity of $P$ on the
disjoint sets $A \setminus B$, $A \cap B$, and $B \setminus A$.  I am not
including a picture in this note.  The point, though, is that if $A$ and $B$
overlap, then $A \cap B$ is counted twice (\emph{overcounted}) in $P(A \cap
B)$, so we need to subtract off $P(A \cap B)$ to compensate.

\begin{center}* * *\end{center}

Now for the induction step.  Suppose the inclusion-exclusion formula is true
for $1, 2, \ldots, n-1$ (we'll only need $2$ and $n-1$), and show it's true for
$n$.  Notationally, this is a mess.  I'll do the $n=3$ case since it is easier
to understand.  This will illuminate how to proceed in the messier general
case.

For $n=3$, we are asked to show that
$$
	P(A \cup B \cup C) = P(A) + P(B) + P(C) - P(A\cap B) - P(A \cap C) - P(B \cap C)
	+ P(A \cap B \cap C).
$$
Since we want to use induction, we can try to isolate $C$ from $A$ and $B$.
We can write
\begin{eqnarray*}
	P((A \cup B) \cup C) = & P(A) + P(B) &+ P(C) \\
	&-P(A\cap B)   &- P(A \cap C) - P(B \cap C) \\
	&&+ P(A \cap B \cap C).
\end{eqnarray*}
We have
$$
	P(A) + P(B) - P(A \cap B) = P(A \cup B)
$$
by the induction hypothesis at $n-1=2$.  (By isolating terms with $C$, we have
found terms involving one fewer set).  For the moment, to make things a little
clearer, write $X = A \cup B$.  Then we need to show that
$$
	P(X \cup C) = P(X) + P(C) - P(A \cap C) - P(B \cap C) + P(A \cap B \cap C).
$$
Using the induction hypothesis for the two sets $X$ and $C$, we know that
$$
	P(X \cup C) = P(X) + P(C) - P(X \cap C).
$$
Looking at these last two equations --- the first of which we need to prove, and
the second of which we already know is true --- we see that we'll be done if
only we can show that
$$
	- P(A \cap C) - P(B \cap C) + P(A \cap B \cap C) = - P(X \cap C).
$$
Toggling the negative signs, this is
$$
	P(X \cap C) = P(A \cap C) + P(B \cap C) - P(A \cap B \cap C).
$$
I put $X=A \cup B$ only for convenience; I'm done with it now.  The statement I
need to prove is
$$
	P((A \cup B) \cap C) = P(A \cap C) + P(B \cap C) - P(A \cap B \cap C).
$$
The trick is that
$$
	A \cap B \cap C = (A \cap C) \cap (B \cap C)
$$
and
$$
	(A \cup B) \cap C = (A \cap C) \cup (B \cap C).
$$
That is, I distribute the $C$'s.  So, the statement I need to prove is
$$
	P((A \cap C) \cup (B \cap C)) = P(A \cap C) + P(B \cap C) - P((A \cap C) \cap (B \cap C)).
$$
Now we again have one fewer set involved:  this is the inclusion-exclusion
formula for the \emph{two} sets $(A \cap C)$ and $(B \cap C)$.  Thus this
statement is true by the induction hypothesis.  And, that was the last thing we
needed to prove.

\begin{center}* * *\end{center}

Now, guided by the $n=3$ case, we can confidently wade into the morass of
subscripts which is the induction step.  We are asked to show that
$$
	P(\cup_{i=1}^n A_i) =
		\sum_{1 \le i \le n} P(A_i)
		- \sum_{1 \le i < j \le n} P(A_i \cap A_j)
		+ \sum_{1 \le i < j < k \le n} P(A_i \cap A_j \cap A_k)
		- \ldots
		+ (-1)^{n+1} P(A_1 \cap \ldots \cap A_n).
$$
Since we want to use induction, we can try to isolate $A_n$ from the others.
We can write
$$
\displaystyle
\begin{array}{lll}
	P((\cup_{i=1}^{n-1} A_i) \cup A_n) =
		&\sum_{1 \le i \le n-1} P(A_i)
		&+ P(A_n) \\
		\\%
		&- \sum_{1 \le i < j \le n-1} P(A_i \cap A_j)
		&- \sum_{1 \le i \le n-1} P(A_i \cap A_n) \\
		\\%
		&+ \sum_{1 \le i < j < k \le n-1} P(A_i \cap A_j \cap A_k)
		&+ \sum_{1 \le i < j \le n-1} P(A_i \cap A_j \cap A_n) \\
		\\%
		&- \ldots
		&- \ldots \\
		\\
		&+(-1)^n P(A_1 \cap \ldots \cap A_{n-1})
		&+(-1)^n \sum_{1 \le i \le n-1} P(A_1 \cap \ldots \cap \hat{A}_i\cap\ldots\cap A_{n-1}\cap A_n) \\
		\\%
		&
		&+ (-1)^{n+1} P(A_1 \cap \ldots \cap A_n).
\end{array}
$$
where the notation $\hat{A}_i$ means omit the $A_i$ from the intersection.
We have
$$
	P(\cup_{i=1}^{n-1} A_i) =
		\sum_{1 \le i \le {n-1}} P(A_i)
		- \sum_{1 \le i < j \le {n-1}} P(A_i \cap A_j)
		+ \sum_{1 \le i < j < k \le {n-1}} P(A_i \cap A_j \cap A_k)
		- \ldots
		+ (-1)^{n} P(A_1 \cap \ldots \cap A_{n-1})
$$
by the induction hypothesis at $n-1$.  (By isolating terms with $A_n$, we have
again found terms involving one fewer set).  As above, for clarity, temporarily
write $X = \cup_{i=1}^{n-1}$.  Then we need to show that
\begin{eqnarray*}
	P(X \cup A_n) &=& P(X) + P(A_n) \\
		&&- \sum_{1 \le i \le n-1} P(A_i \cap A_n) \\
		&&+ \sum_{1 \le i < j \le n-1} P(A_i \cap A_j \cap A_n) \\
		&&- \ldots \\
		&&+(-1)^n \sum_{1 \le i \le n-1} P(A_1 \cap \ldots \cap \hat{A}_i\cap\ldots\cap A_{n-1}\cap A_n) \\
		&&+ (-1)^{n+1} P(A_1 \cap \ldots \cap A_n).
\end{eqnarray*}
Using the induction hypothesis for the two sets $X$ and $A_n$, we know that
$$
	P(X \cup A_n) = P(X) + P(A_n) - P(X \cap A_n).
$$
Looking at these last two equations --- the first of which we need to prove, and
the second of which we already know is true --- we see that we'll be done if
only we can show that
\begin{eqnarray*}
		&&- \sum_{1 \le i \le n-1} P(A_i \cap A_n) \\
		&&+ \sum_{1 \le i < j \le n-1} P(A_i \cap A_j \cap A_n) \\
		&&- \ldots \\
		&&+(-1)^n \sum_{1 \le i \le n-1} P(A_1 \cap \ldots \cap \hat{A}_i\cap\ldots\cap A_{n-1}\cap A_n) \\
		&&+ (-1)^{n+1} P(A_1 \cap \ldots \cap A_n) \\
		&=& - P(X \cap A_n).
\end{eqnarray*}
Toggling the negative signs, this is
\begin{eqnarray*}
		P(X \cap A_n)
		&=&
		\sum_{1 \le i \le n-1} P(A_i \cap A_n) \\
		&&- \sum_{1 \le i < j \le n-1} P(A_i \cap A_j \cap A_n) \\
		&&+ \ldots \\
		&&-(-1)^n \sum_{1 \le i \le n-1} P(A_1 \cap \ldots \cap \hat{A}_i\cap\ldots\cap A_{n-1}\cap A_n) \\
		&&- (-1)^{n+1} P(A_1 \cap \ldots \cap A_n).
\end{eqnarray*}
Note that $-(-1)^n$ is the same as $(-1)^{n-1}$.  So we need to show
\begin{eqnarray*}
		P(X \cap A_n)
		&=&
		\sum_{1 \le i \le n-1} P(A_i \cap A_n) \\
		&&- \sum_{1 \le i < j \le n-1} P(A_i \cap A_j \cap A_n) \\
		&&+ \ldots \\
		&&+(-1)^{n-1} \sum_{1 \le i \le n-1} P(A_1 \cap \ldots \cap \hat{A}_i\cap\ldots\cap A_{n-1}\cap A_n) \\
		&&+ (-1)^{n} P(A_1 \cap \ldots \cap A_n).
\end{eqnarray*}

As before, I don't need to write $X = \cup_{i=1}^{n-1}$ anymore.  The statement
I need to prove is
\begin{eqnarray*}
		P((\cup_{i=1}^{n-1} A_i) \cap A_n)
		&=&
		\sum_{1 \le i \le n-1} P(A_i \cap A_n) \\
		&&- \sum_{1 \le i < j \le n-1} P(A_i \cap A_j \cap A_n) \\
		&&+ \ldots \\
		&&+(-1)^{n-1} \sum_{1 \le i \le n-1} P(A_1 \cap \ldots \cap \hat{A}_i\cap\ldots\cap A_{n-1}\cap A_n) \\
		&&+ (-1)^{n} P(A_1 \cap \ldots \cap A_n).
\end{eqnarray*}
The distribution tricks are
$$
	A_1 \cap \ldots \cap A_n = (A_1 \cap A_n) \cap \ldots \cap (A_{n-1} \cap A_n)
$$
and
$$
	(A_1 \cup \ldots \cup A_{n-1}) \cap A_n = (A_1 \cap A_n) \cup \ldots \cup (A_{n-1} \cap A_n).
$$
So, the statement I need to prove is
\begin{eqnarray*}
		P(\cup_{i=1}^{n-1} (A_i \cap A_n))
		&=&
		\sum_{1 \le i \le n-1} P(A_i \cap A_n) \\
		&&- \sum_{1 \le i < j \le n-1} P((A_i \cap A_n) \cap (A_j \cap A_n)) \\
		&&+ \ldots \\
		&&+(-1)^{n-1} \sum_{1 \le i \le n-1} P((A_1 \cap A_n) \cap\ldots\cap (\hat{A}_i\cap A_n) \cap\ldots\cap (A_{n-1}\cap A_n)) \\
		&&+ (-1)^{n} P((A_1 \cap A_n) \cap \ldots \cap (A_{n-1} \cap A_n)).
\end{eqnarray*}
Now we again have one fewer set involved:  this is the inclusion-exclusion
formula for the $n-1$ sets $(A_1 \cap A_n)$ through $(A_{n-1} \cap A_n)$.  Thus
this statement is true by the induction hypothesis.  Since that is all that
remained to be shown, we are done.
\end{proof}
\end{prop*}
