1. ## Bonferroni's Inequality Proof

Hello,

I am confused with the following question.

Suppose $\displaystyle E_1, E_2,..., E_n$ are events, then

$\displaystyle \sum_{i=1}^{n} P(E_i) - \sum_{i<j}P(E_i E_j) \leq P(\cup_{i=1}^{n}E_i) \leq \sum_{i=1}^{n} P(E_i)$

The right hand side is Boole's inequality. Prove the left hand side.

I am trying to prove this using induction, but I am not sure if I am doing it correctly.
For $\displaystyle n=2$,
Let $\displaystyle E_1$ and $\displaystyle E_2$ be events,
then, $\displaystyle \sum_{i=1}^{2} P(E_i) - \sum_{i<j}P(E_i E_j) = P(E_1) + P(E_2) - P(E_1 E_2) = P(E_1 \cup E_2)$.
Thus, this holds true for $\displaystyle n=2$.

Am I going on the right track?
Any suggestion for the inductive step?

2. If I prove the Inclusion-Exclusion formula

$\displaystyle \sum_{i=1}^{n}P(E_i)-\sum_{i<j}P(E_i E_j) + \sum_{i<j<k}P(E_i E_j E_k) - ... +(-1)^{n-1}P(\cap_{i=1}^{n} E_i)= P(\cup_{i=1}^{n} E_i)$

how can I get the following inequality?

$\displaystyle \sum_{i=1}^{n} P(E_i) - \sum_{i<j}P(E_i E_j) \leq P(\cup_{i=1}^{n}E_i)$

3. have u solved the problem?

Interested to know how to do this too