# Proof of a Bonferroni inequality

Here is a very enjoyable theorem due to Bonferroni. Let $$n \geq 2$$ and consider the probability triple $$(\Omega, \mathcal{F}, P)$$ and a collection of sets of $$\Omega$$ in $$\mathcal{F}$$ denoted $$( A_i )_{i=1}^n$$. Then the following holds:

### Proof

By induction. The case where $$n = 2$$ is obvious. Assume the inequality holds up to $$n$$ and denote $$B = \bigcup_{i = 1}^n A_i$$. Then the base case implies

Using the distributive law, this becomes

which, by Boole’s inequality, is less than or equal to $$\sum_{i=1}^n P(A_{n + 1} \cap A_i)$$. So,

by the inductive hypothesis. Simplifying, we note that the term $$\sum_{i=1}^n P(A_{n + 1} \cap A_i)$$ is the increment of the sum over $$i < j$$ in the inequality, thus resulting in

which was to be proved.

Written on September 2, 2017