Let $\displaystyle A_{1}, A_{2},...., A_{n}$ be a set of n events (n>1). Use induction to prove:

$\displaystyle \sum_{i=1}^{n} P(A_{i}) - \sum_{i<j} P(A_{i}A_{j}) \leq P(\bigcup_{i=1}^{n} A_{i}) \leq \sum_{i=1}^{n} P(A_{i})$.

Note that if n = 3:

$\displaystyle \sum_{i<j} P(A_{i}A_{j} = P(A_{1}A_{2}) + P(A_{1}A_{3}) + P(A_{2}A_{3})$.