Proving that $P\left ( \bigcup_{i=1}^{n}A_{i} \right )\leq \sum_{i=1}^{n}P(A_{i})$ by induction

Question

Proposition 1: Let $A_{1},\dots, A_{n}$ be events in the probability space $(\Omega,\mathcal{F},P)$. Then $$P\left ( \bigcup_{i=1}^{n}A_{i} \right )\leq \sum_{i=1}^{n}P(A_{i}).$$

Let's start with a lemma.

Lemma 1: Let $A$ and $B$ be events in $\mathcal{F}$. Then $P(A\cup B)\leq P(A)+P(B)$.

(Fast) proof to Lemma 1: Note that $A\cup B = (A\setminus (A\cap B))\cup B$ and $(A\setminus (A\cap B))\cap B= \emptyset$, then $$ P(A\cup B)=P(A\setminus (A\cap B))+P(B)=P(A)-P(A\cap B)+P(B). $$ Since $P(A\cap B)\geq 0$, we have $0\leq P(A)+P(B)-P(A\cup B)$. $\blacksquare $

Proof to Proposition 1: Let $Q(n)$ denote the statement. We wish to prove it by induction that $Q(n)$ is true for all $n\geq 2$. The statement $Q(2)$ is clearly true, see Lemma 1. Assume now that $Q(k)$ is true for some $k\geq 2$. Let $B=\bigcup_{i=1}^{k}A_{i}$, and we see that \begin{align*} P\left ( \bigcup_{i=1}^{k+1}A_{i} \right )&=P(B\cup A_{k+1})\\ &\leq P(B)+P(A_{k+1})\tag{Lemma 1}\\ &= P\left ( \bigcup_{i=1}^{k}A_{i} \right )+P(A_{k+1})\\ &\leq \sum_{i=1}^{k}P(A_{i})+P(A_{k+1})\tag{assumption}\\ &=\sum_{i=1}^{k+1}P(A_{i}), \end{align*} which shows that $Q(k+1)$ is true. Hence the statement $Q(n)$ is true for all $n\geq 2$. $\blacksquare $

Question(s): I doubt if $n=1$ should have been shown too, since it's trivial. How is the proof so far?

Answer 1

The question as asked has been answered in the comments; I will use this space here to expand on a discussion about induction that developed there.

Suppose you want to prove some statement $P(n)$ for all natural $n$. Proof by induction is a proof technique by which we show $P(k)$ being true implies $P(k+1)$ is true, so if we can prove that $P$ is true for some natural number, it is true for all the naturals that follow it: $P(1)$ is true because we prove it, $P(2)$ is true because $P(1)$ implies it by the inductive step; $P(3)$ is true because $P(2)$ implies it, and so on.

However, sometimes it is hard to deduce $P(k+1)$ just by assuming $P(k)$. Well, can we use any other information? It turns out we can: we can use all the $P(n)$ back down to our base case! That is, if we can prove that assuming $P(k)$ and the extra things $P(1)$,$P(2)$,$P(3) \ldots P(k-1)$ implies $P(k+1)$, then we still get to deduce that the proposition is true by induction! This is called Strong Induction, because you it looks like you are making stronger assumptions than you are in Weak (normal) induction. It's not easy to prove that these two techniques are equivalent, you can find a proof easily online or you can just believe me.

So how is this relevant? Well in your proof you use the inductive step twice: once is the usual way, in your second to last line. But the lemma you proved at the beginning is also an example of the inductive hypothesis when $n=2$. It's completely fine to prove the $n=2$ case as a lemma and deduce the theorem by weak induction. Your proof is correct.

However, Clement and I were trying to point out that you don't have to do this anyway! Because you can use that technique of strong induction to assume both that $P(2)$ is true and $P(k)$ is true to deduce that $P(k+1)$ is true. That's all we were trying to explain.

Answer 2

Since you say $(\Omega, \mathcal{F}, P)$, indicating that when you say probability space you mean the modern measure theoretic definition and not the elementary probability definition, I feel obligated to give a better approach.

There is no need to use induction. The definition of $P$ being a measure includes the fact that for $E_i$ a countable pairwise disjoint family $$ P\left(\bigcup_{i=1}^\infty E_i\right) = \sum_{i=1}^\infty P(E_i). $$ This is called countable additivity and it is the defining property of a measure. Now consider $A_i$ that are not disjoint. Define $A_1' = A_1$ and recursively $A_i' := A_i\setminus \cup_{k=1}^{i-1}A_k$. Think $A_i'$ is the part of $A_i$ that hasn't been covered yet. Then the $A_i'$ are disjoint and $\cup_{i=1}^\infty A_i = \cup_{i=1}^\infty A_i'$ so $$ P\left(\bigcup_{i=1}^\infty A_i\right) = P\left(\bigcup_{i=1}^\infty A_i'\right) = \sum_{i=1}^\infty P(A_i') \leq \sum_{i=1}^\infty P(A_i). $$
Where here we used the lemma that if $A \subseteq B$ then $P(A) \leq P(B)$ because $A = (A\setminus B) \cup B$ so $P(A) = P(A\setminus B) + P(B) \geq P(B)$. Note that in order to get the result for a finite collection $A_1,\ldots,A_n$, simply define $A_{n+k}:= \emptyset$ for all $k>0$.