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$$.