### Proof Bonferroni’s Inequality

Let $E_s$ be an event that occurs with probability $1-\alpha_s$ for $s=1,2,...,k$.  Then $P(\bigcap_{s=1}^k E_s) \geq 1- \sum_{s=1}^k \alpha_s$  where $\bigcap_{s=1}^k E_s$ is the intersection of non-independent events $E_1, E_2, ..., E_k$.

### Proof by induction on n

Base case, $n=2$

$P(E_1 \cup E_2)= P(E_1) + P(E_2) - P(E_1 \cap E_2) \leq 1$

By additivity law and probability axiom

$P(E_1 \cap E_2) \geq P(E_1) + P(E_2) -1$
$\geq (1-\alpha_1)+(1-\alpha_2)-1$
$\geq (1-\alpha_1 - \alpha_2)$

Inductive hypothesis

Suppose relation is true for $n=k-1$, that is

$P(\bigcap_{s=1}^{k-1}E_s) \geq 1- \sum_{s=1}^{k}\alpha_s$

Inductive Step

Let $A = {\bigcap_{s=1}^{k-1}E_s}$.  Then $P(A) = 1-\sum_{s=1}^{k-1}\alpha_s$

$P(\bigcap_{s=1}^{k}E_s) = P(A\cap E_k)$
$\geq P(A) + P(E_k)-1$
$\geq \displaystyle 1- \sum_{s=1}^{k-1}\alpha_s + (1-\alpha_k) - 1$
$\geq \displaystyle1- \sum_{s=1}^{k-1}\alpha_s -\alpha_k$
$\geq \displaystyle1- \sum_{s=1}^{k}\alpha_s$

as required.