- #1

mahler1

- 222

- 0

## Homework Statement

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

## 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.