In this quick probability post, we are going to prove the union bond. In probability, it can be very helpful to set some bounds since it can be hard to find the exact probability.
The union bound states that if we have a collection of sets A₁, A₂, … AN, then:
Proof
We prove this by induction. We start with the base of N=2:
The inequality is true because probability is a non-negative number. After proving for the base case, we assume that the argument is true for some N, and we want to prove for N+1
By the induction assumption for N, we know
and therefore
And so, by the principle of induction, the statement has been proved.
