Homework Help: Exclusion-inclusion formula in probability

1. Aug 24, 2014

mahler1

1. The problem statement, all variables and given/known data

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)$

3. The attempt at a solution

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 define $B_1=A_1,\ldots,B_{n-1}=A_{n-1},B_n=A_n\cup A_{n+1}$. We have

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

This equals to $\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)+\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k-1} (-1)^{k}P(\bigcap_{i \in \mathcal J} A_i \cap (A_n \cup A_{n+1}))$

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

I don't know how to reduce this expression to the one I need to, which is:

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

I would really appreciate some help to finish the problem.

2. Aug 24, 2014

Ray Vickson

Instead of trying to jump immediately to the general case, first try the simple cases of going from n=2 to n=3 and from n=3 to n=4 (and no, I am not joking). That way, you will see what is happening, and be able to grasp how to go the the general case of n to (n+1).