Generalized Formula for the Probability of the Union of $n$ events occurring? Consider
$$
P(A \cup B) = P(A) + P(B) - P(A \cap B)
$$
What is the generalization of this formula for $n$ events occuring? That is
$$
P(\cup A_i) = \sum P(A_i) + \ldots ?
$$
 A: We have 
\begin{align}
P(A_1\cup A_2\cup A_3)= & \;\;\;\;P(A_1)+P(A_2) +P(A_3) 
\\
&
-\underbrace{P(A_1\cap A_{2})}_{1<2}
-\underbrace{P(A_1\cap A_{3})}_{1<3}
-\underbrace{P(A_2\cap A_{3})}_{2<3} 
\\
&
+\underbrace{P(A_1\cap A_{2}\cap A_{3})}_{1<2<3}
\end{align}
and
\begin{align}
P(A_1\cup A_2\cup A_3\cup A_4)= & \;\;\;\;P(A_1)+P(A_2) +P(A_3)+P(A_4) 
\\
&
-\underbrace{P(A_{1}\cap A_{2})}_{1<2}
-\underbrace{P(A_{1}\cap A_{3})}_{1<3}
-\underbrace{P(A_{1}\cap A_{4})}_{1<4}
\\
&
-\underbrace{P(A_{2}\cap A_{3})}_{2<3}
-\underbrace{P(A_{2}\cap A_{4})}_{2<4}
\\
&
-\underbrace{P(A_{3}\cap A_{4})}_{3<4}
\\
&
+\underbrace{P(A_{1}\cap A_{2}\cap A_{3})}_{1<2<3}
+\underbrace{P(A_{1}\cap A_{2}\cap A_{4})}_{1<2<4}
+\underbrace{P(A_{1}\cap A_{3}\cap A_{4})}_{1<3<4}
+\underbrace{P(A_{1}\cap A_{2}\cap A_{4})}_{2<3<4}
\\
&
-\underbrace{P(A_1\cap A_{2}\cap A_{3}\cap A_4)}_{1<2<3<4}.
\end{align}
In geral, 
\begin{align}
P\Big( \bigcup_{i=1}^{n}A_i\Big)
=&-(-1)^1\sum_{i{_1}=1}^{n}P(A_{i_1})
\\
&-(-1)^2\sum_{1\leq i{_1}<i_{_2}\leq n}^{n}P(A_{i_1}\cap A_{i_2})
\\
&-(-1)^3\sum_{1\leq i{_1}<i_{_2}<i_{_3}\leq n}^{n}P(A_{i_1}\cap A_{i_2}\cap A_{i_3})
\\
&-(-1)^4\sum_{1\leq i{_1}<i_{_2}<i_{_3}<i_{_4}\leq n}^{n}P(A_{i_1}\cap A_{i_2}\cap A_{i_3}\cap A_{i_4})
\\
&\quad\quad\quad\vdots
\\
&\ldots-(-1)^n \sum_{1\leq i_{1}<i_{2}<i_{3}<\ldots <i_{n}\leq n}^{n}P(A_{i_1}\cap A_{i_2}\cap A_{i_3}\cap \ldots \cap A_{i_n})
\end{align}
A: The inclusion-Exclusion principle, namely for set of three event $\{A_i\}_{i=1}^3$, then 
\begin{align}
P(A_1 \cup A_2 \cup A_3) =& P(A_1) + P(A_2) + P(A_3)\\
                          -& P(A_1 \cap A_2) - P(A_1 \cap A_3) -P(A_2 \cap A_3)\\
                          +&P(A_1) + P(A_2) + P(A_3).  
\end{align}
Now, you can use induction to show the result for general set of $n$ events, $\{A_i\}_{i=1}^n$, 
\begin{align}
P\left( \bigcup_{i=1}^n A_i \right) = \sum_{i=1}^n P(A_i) - \sum_{i <j}P(A_i \cap A_j) + \cdots + (-1)^{n+1}P(\cap_{i=1}^nA_i).
\end{align}
