# prove by induction that $P\left(\bigcup\limits_{i=1}^{n} E_i\right) = 1-\prod\limits_{i=1}^{n}(1-P(E_i))$, $E_1,E_2,\ldots , E_i$ independent

Suppose $E_1,E_2,\ldots , E_i$ are independent events. prove by induction that $$P\left(\bigcup\limits_{i=1}^{n} E_i\right) = 1-\prod\limits_{i=1}^{n}(1-P(E_i))$$

The first step is easy. For $n=1$ we have $$P\left(\bigcup\limits_{i=1}^{1} E_i\right) = P(E_1)= 1-(1-P(E_i))=1-\prod\limits_{i=1}^{1}(1-P(E_i))$$ I don't really see how to continue from here though. Any help would be appreciated!

• You can write $\bigcup_{i=1}^n E_i$ as $E_n \cup \bigcup_{i=1}^{n-1} E_i$. Then the right term is the union of only $n-1$ elements, so from the induction hypothesis it follows that...
– fgp
May 16, 2013 at 21:32
• The natural thing to do is to work with complements. If we want to work directly with the unions, the case $n=2$ is critical. May 16, 2013 at 21:36
• it would be easy to prove using De Morgan's laws but I need to use induction. May 16, 2013 at 21:58

We note that: $$P\left(\bigcup\limits_{i=1}^{1} E_i\right) = P(E_1)= 1-(1-P(E_i))=1-\prod\limits_{i=1}^{1}(1-P(E_i))$$ Now suppose for a certain $k \in \mathbb{N}$ that: $$P\left(\bigcup\limits_{i=1}^{k} E_i\right) = 1-\prod\limits_{i=1}^{k}(1-P(E_i))$$ So $$P\left(\left(\bigcup\limits_{i=1}^{k} E_i\right)^c\right)=\prod\limits_{i=1}^{k}(1-P(E_i))$$ Now for $k+1$ we have: $$P\left(\bigcup\limits_{i=1}^{k+1} E_i\right)=P\left(E_{k+1}\cup\left(\bigcup\limits_{i=1}^{k} E_i\right)\right)$$ Now we use that $P(A\cap B) = P(A)P(B)$ for independent $A$ and $B$, and the fact that if all $E_i$ are independent then so are the events $E_i^c$: $$P\left(E_{k+1}^c\cap (\left(\bigcup\limits_{i=1}^{k} E_i\right)^c\right)=(1-P(E_{k+1}))\prod\limits_{i=1}^{k}(1-P(E_i))=\prod\limits_{i=1}^{k+1}(1-P(E_i))$$ Finally we use the fact that $P(A ^c\cap B^c)=P(A\cup B)^c$ so $$P\left(E_{k+1}^c\cap (\left(\bigcup\limits_{i=1}^{k} E_i\right)^c\right) = 1 - P\left(E_{k+1}\cup\left(\bigcup\limits_{i=1}^{k} E_i\right)\right)=1 - P\left(\bigcup\limits_{i=1}^{k+1} E_i\right)$$ Combining these results we have $$1 - P\left(\bigcup\limits_{i=1}^{k+1} E_i\right) = \prod\limits_{i=1}^{k+1}(1-P(E_i))$$ or $$P\left(\bigcup\limits_{i=1}^{k+1} E_i\right) = 1-\prod\limits_{i=1}^{k+1}(1-P(E_i)).$$ Now by induction we have $$P\left(\bigcup\limits_{i=1}^{n} E_i\right) = 1-\prod\limits_{i=1}^{n}(1-P(E_i))$$ for all $n \in \mathbb{N}$.
As a set theoric proposition, it's not hard to prove that $\cup_{i=1}^n E_i=(\cap_{i=1}^n {E_i}^c)^c$. So $P(\cup_{i=1}^n E_i)=P((\cap_{i=1}^n {E_i}^c)^c)=1-P((\cap_{i=1}^n {E_i}^c)$. The $E_i$'s are independent, hence their complements are independent, too. So the latter term equals to $1-\Pi_{i=1}^n P({E_i}^c)=1-\Pi_{i=1}^n (1-P(E_i))$. QED.