Proving the probability of a union of sets with mathematical induction

Question

The question is to prove using induction that $$P(\bigcup_{i=1}^n E_n) \le \sum_{i=1}^n P(E_n)$$ I've gotten the basic step and the inductive hypothesis, but I'm stuck at the final stage. What I arrive at is $$P(\bigcup_{i=1}^{k+1} E_{k+1}) \le P(\bigcup_{i=1}^k E_k) + P(E_{k+1})$$

I don't know how to move on from here as I am not sure if $$P(\bigcup_{i=1}^k E_k) \, and \, P(E_{k+1})$$ can be combined.

Answer 1

Notice that

$$E_1 \cup E_2 = E_1 \cup (E_2\setminus E_1)$$

$$E_1 \cup E_2 \cup E_3= E_1 \cup (E_2\setminus E_1) \cup \big(E_3\setminus (E_1\cup E_2)\big)$$

and so on. Notice that each union on the RHS is a disjoint union. Moreover, notice that $E_2\setminus E_1 \subset E_2$ and $E_3\setminus (E_1\cup E_2) \subset E_3$. Do you think you can finish?

Answer 2

The question is to prove using induction that $$P(\bigcup_{i=1}^n E_n) \le \sum_{i=1}^n P(E_n)$$

No. Watch your subscripts. What you should be trying to prove is that $$\mathsf P(\bigcup_{i=1}^n E_i)\leq\sum_{i=1}^n\mathsf P(E_i)$$

I've gotten the basic step and the inductive hypothesis, but I'm stuck at the final stage. What I arrive at is $$P(\bigcup_{i=1}^{k+1} E_{k+1}) \le P(\bigcup_{i=1}^k E_k) + P(E_{k+1})$$

$$\mathsf P(\bigcup_{i=1}^{k+1} E_i) \le \mathsf P(\bigcup_{i=1}^k E_i) + \mathsf P(E_{k+1})\tag 1$$

Because: $\bigcup_{i=1}^{k+1}E_i=(\bigcup_{i=1}^k E_i)\cup E_{k+1}$ and the probability for a union of two sets is at least as great as the sum of the probabilities for each set.

(Because for any sets $A,B$, we have $\mathsf P(A\cup B) = \mathsf P(A)+\mathsf P(B)-\mathsf P(A\cap B)$, since ….)

I don't know how to move on from here

Substitute.

You use the above to show that if $$~\mathsf P(\bigcup_{i=1}^k E_i)\leq\sum_{i=1}^{k}\mathsf P(E_i)~\tag 2$$, then $$~\mathsf P(\bigcup_{i=1}^{k+1} E_i)\leq\sum_{i=1}^{k+1}\mathsf P(E_i)~\tag 3$$.