These problems and Proofs are adapted from the textbook: Probability and Random Process by Scott Miller 2ed

Problem-1: Proof that for events A and B the following holds:

$Pr\left(A\cup B\right) = Pr\left(A\right)+Pr\left(B\right)-Pr\left(A\cap B\right)$

Solution: First, note that the sets $A\cup B$ and $B$ can be rewritten as

$A\cup B=\{A\cup B\}\cap\{\overline{B}\cup B\}=\{A\cap\overline{B}\}\cup B$

$B=B\cap\{A\cup\overline{A}\}=\{A\cap B\}\cup\{\overline{A}\cap B\}.$

Hence, $A\cup B$ can be expressed as the union of three mutually exclusive sets.

$A\cup B=\{\overline{B}\cap A\}\cup\{A\cap B\}\cup\{\overline{A}\cap B\}$

Next, rewrite $\overline{B}\cap A$ as

$\overline{B} \cap A= \{\overline{B}\cap A\}\cup\{\overline{A}\cap A\}= A\cap\{\overline{A}\cup\overline{B}\} = A\cap\{\overline{A\cap B}\}$

Likewise, $\overline{A}\cap B=B\cap\{\overline{A\cap B}\}$. Therefore $A\cup B$ can be rewritten as the following union of three mutually exclusive sets:

$A\cup B=\{A\cap(\overline{A\cap B})\}\cup\{A\cap B\}\cup\{B\cap(\overline{A\cap B})\}$

Hence
$\begin{eqnarray*}Pr\left(A\cup B\right)=Pr\left(A\cap(\overline{A\cap B})\right)+Pr\left(A\cap B\right)+Pr\left(B\cap(\overline{A\cap B})\right).\end{eqnarray*}$

Next, write A as the union of the following two mutually exclusive sets

$A=\{A\cap\{\overline{A\cap B}\}\}\cup\{A\cap B\}$

Hence,

$Pr\left(A\right)=Pr\left(A\cap\{\overline{A\cap B}\}\right)+Pr\left(A\cap B\right)$

and

$Pr\left(A\cap\{\overline{A\cap B}\}\right)=Pr\left(A\right)-Pr\left(A\cap B\right).$

Likewise,

$Pr\left(B\cap\{\overline{A\cap B}\}\right)=Pr\left(B\right)-Pr\left(A\cap B\right).$

Finally,

$\begin{eqnarray*}Pr\left(A\cup B\right) & = & Pr\left(A\cap(\overline{A\cap B})\right)+Pr\left(A\cap B\right)+Pr\left(B\cap(\overline{A\cap B})\right)\\ & = & \left(Pr\left(A\right)-Pr\left(A\cap B\right)\right)+Pr\left(A\cap B\right)+Pr\left(B\right)-Pr\left(A\cap B\right)\\ & = & Pr\left(A\right)+Pr\left(B\right)-Pr\left(A\cap B\right). \end{eqnarray*}$

Problem-2: Show that the Problem-1 can be generalized upto three events:

$Pr(A\cup B\cup C) = Pr(A)+Pr(B)+Pr(C)-Pr(A\cap B)-Pr(A\cap C)-Pr(B\cap C)+Pr(A\cap B\cap C)$

Solution:

$\begin{eqnarray*} {Pr(A\cup B\cup C)}\\ & = & Pr((A\cup B)\cup C)\\ & = & Pr(A\cup B)+Pr(C)-Pr((A\cup B)\cap C)\\ & = & Pr(A)+Pr(B)-Pr(A\cap B)+Pr(C)-Pr((A\cap C)\cup(B\cap C))\\ & = & Pr(A)+Pr(B)+Pr(C)-Pr(A\cap B)-Pr((A\cap C)\cup(B\cap C))\\ & = & Pr(A)+Pr(B)+Pr(C)-Pr(A\cap B)\\ & – & \left(Pr((A\cap C)+Pr(B\cap C))-Pr(A\cap C\cap B\cap C)\right)\\ & = & Pr(A)+Pr(B)+Pr(C)-Pr(A\cap B)-Pr(A\cap C)-Pr(B\cap C)+Pr(A\cap B\cap C) \end{eqnarray*}$

Problem-3: Prove that if  $A \subset B \; \text{then} \; Pr(A) \leq Pr(B)$

Solution: Since $A\subset B$ and $A\cap B=A$, $B=A\cup\{B\cap\overline{A}\}$.
Since $A$ and $B\cap\overline{A}$ are mutually exclusive, we have
$\begin{eqnarray} Pr(B)=Pr(A)+Pr(B\cap\overline{A})\ .\label{eq1} \end{eqnarray}$
Hence by (\eqref{eq1}) and considering $Pr(B\cap\overline{A})\ge0$, $Pr(A)\le Pr(B)$.

Problem-4: Prove the union bound which states that for any events $A_1,A_2,\ldots,A_M$ (not necessarily mutually exclusive),

$Pr\left(\bigcup_{i=1}^{M}\right)\leq\sum_{i=1}^{M}Pr(A_{i})$

Solution:  We shall prove this by induction. For $k=1$ this reduces to
$Pr(A_{1})\leq Pr(A_{1})$
which is obviously true.For $k=2$ we have
$Pr(A_{1}\cup A_{2})=Pr(A_{1})+Pr(A_{2})-Pr(A_{1}\cap A_{2})$
by the axioms of probability.
$\Rightarrow Pr(A_{1}\cup A_{2})\leq Pr(A_{1})+Pr(A_{2})$
The equality holding when the events are mutually exclusive. Assume that the propostion is true for $M=k$. Then we have
$Pr\left(\bigcup_{i=1}^{k}A_{i}\right)\leq\sum_{i=1}^{k}Pr(A_{i})$
We shall prove that this is true for $M=k+1$. Let  $B=\bigcup_{i=1}^{k}A_{i}$
Then the following holds
\begin{eqnarray}
Pr(B)\leq\sum_{i=1}^{k}Pr(A_{i})\label{eqP4_1}
\end{eqnarray}
Since the proposition is true for $M=2$
\begin{eqnarray}
Pr(B\cup A_{k+1})\leq Pr(B)+Pr(A_{k+1})\label{eqP4_2}
\end{eqnarray}
Using $(\eqref{eqP4_1})$ in ($\eqref{eqP4_2}$) we have
$Pr(B\cup A_{k+1})\leq\sum_{i=1}^{k}Pr(A_{i})+Pr(A_{k+1})$
$Pr(\bigcup_{i=1}^{k+1}A_{i})\leq\sum_{i=1}^{k}Pr(A_{i})+Pr(A_{k+1})$
$Pr(\bigcup_{i=1}^{k+1}A_{i})\leq\sum_{i=1}^{k+1}Pr(A_{i})$
Thus the proposition is true for $M=k+1$ and by the principle of induction it is true for all finite $M$.