The union bound, also known as Boole’s inequality, says that for a countable set of events, the probability that at least one of the events happens is not greater than the sum of the probabilities of the individual events:
Theorem (Union bound): For a countable set of events $A_1, A_2, A_3, \ldots$,
\[\Pr \left(\bigcup _{i=1}^{\infty} A_i \right) \leq \sum_{i=1}^{\infty} \Pr(A_i).\]For two events, this is a straightforward consequence of the fact that
\[\Pr(A \cup B) = \Pr(A) + \Pr(B) - \Pr(A \cap B)\]and probabilities can never be negative. The same argument can be applied via induction to prove the inequality for all $n$.
By applying DeMorgan’s laws, we can obtain the following corollary to the union bound, now applied to intersections:
Corollary: For a finite set of events $A_1, A_2, \ldots, A_n$,
\[\Pr \left(\bigcap _{i=1}^n A_i \right) \ge \sum_{i=1}^n \Pr(A_i) - n + 1.\]