Bonferroni Inequalities

Ponder...

For events in and any , the truncated inclusion-exclusion sums bound from above when is odd and from below when is even; in particular .

Lemma 2.5 (Bonferroni Inequalities)

Let . We have

Let be events in . Then for any ,

Proof

Induction on . The base case is clear. Writing

and applying the induction hypothesis to the two unions of events gives the bound for odd ; the case of even is similar.