Proof of the inclusion-exclusion formula in probability

Let $(\Omega,\mathcal F, P)$ be a probability space and let $A_1,A_2,...,A_n$ be events in $\mathcal F$.

Prove the following inclusion-exclusion formula

$P(\bigcup_{i=1}^nA_i)=\sum_{k=1}^n$ $\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)$

I am trying to prove this formula by induction; for $n=2$, let $A, B$ be two events in $\mathcal F$. We can write $A=(A \setminus B) \cup (A\cap B)$, $B=(B \setminus A) \cup (A\cap B)$, since these are disjoint unions, then

$P(A)=P(A \setminus B)+P(A\cap B)$ and $P(B)=P(B \setminus A)+P(A\cap B)$.

Now, $A \cup B$ can be expressed as $A \cup B= (A\setminus B) \cup (A \cap B) \cup (B \setminus A)$, which it's also union of disjoint sets, so

$P(A \cup B)=P(A \setminus B)+P(A\cap B)+P(B \setminus A)=P(A)+P(B)-P(A \cap B)$.

This proves that for $n=2$, the formula is correct.

Now, I want to show that the formula is true for $n \implies$ the formula is satisfied for $n+1$, I got stuck at this point, maybe I could express $P(\cup_{i=1}^{n+1} A_i)=P((\cup_{i=1}^n A_i \setminus A_{n+1}) \cup A_{n+1})=P(\cup_{i=1}^n A_i \setminus A_{n+1})+P(A_{n+1})$ (1)

I can use the inductive hypothesis on the term $P(\cup_{i=1}^n A_i \setminus A_{n+1})$, so $P(\cup_{i=1}^n (A_i \setminus A_{n+1}))=\sum_{k=1}^n$ $\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} (A_i\setminus A_{n+1}))$

Expression (1) becomes $\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} (A_i\setminus A_{n+1})) +P(A_{n+1})$

I don't know to to take this expression to the one I want, which is

$\sum_{k=1}^{n+1}$ $\sum_{\mathcal J \subset \{1,...,n+1\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)$

I would like to know how to continue this part of the exercise.

Solution 1:

For an alternative to Hamou's approach—and one that's more similar to your initial idea—you can do the following: observe that $P(A\setminus B)=P(A)-P(A\cap B).$ So $$ \begin{aligned} P\left(\bigcup_{i=1}^{n+1}A_i\right)&=P\left(\bigcup_{i=1}^n A_i\right)+P\left(A_{n+1}\setminus\bigcup_{i=1}^n A_i\right)\\ &=P\left(\bigcup_{i=1}^n A_i\right)+P(A_{n+1})-P\left(\bigcup_{i=1}^n (A_i\cap A_{n+1})\right). \end{aligned} $$ Now apply the induction hypothesis to both unions in this last expression.

Solution 2:

Hint: For $n\Rightarrow n+1$: $A_1,\ldots,A_n,A_{n+1}$, take $B_1=A_1,\ldots,A_{n-1}=B_{n-1},B_n=A_n\cup A_{n+1}$ and apply the inductive hypothesis to $B_1,\ldots,B_n$.