Problem:
Show that
$$
P( A_1 \cap A_2 \cap \ldots A_n)
\geq P(A_1) + P(A_2) + \ldots + P(A_n) – (n-1)
$$
Answer:
Recall that:
$$ P(A \cup B) = P(A) + P(B) – P(A \cap B)$$
We can rewrite this as:
$$P(A \cap B) = P(A) + P(B) – P(A \cup B) $$
I am going to prove this by induction on $n$.
case $n = 1$
We need to prove that:
$$ P(A_1) \geq P(A_1) – (1-1)$$
Since $1-1 = 1$ it is obviously true.
case $n = 2$
We need to prove that:
$$ P(A_1 \cap A_2) \geq P(A_1) + P(A_2) – (2-1)$$
We have:
\begin{align*}
P(A_1 \cap A_2) &= P(A_1) + P(A_2) – P(A_1 \cup A_2) \\
P(A_1) + P(A_2) – P(A_1 \cup A_2) &\geq P(A_1) + P(A_2) – 1 \\
P(A_1) + P(A_2) – P(A_1 \cup A_2) &\geq P(A_1) + P(A_2) – (2-1) \\
\end{align*}
Now we assume it for $n = i$. This means we have:
$$ P( A_1 \cap A_2 \cap … A_{i}) \geq P(A_1) + P(A_2) + .. + P(A_{i}) – (i-1) $$
Now we prove it for $n=i+1$. We need to prove that
$$ P( A_1 \cap A_2 \cap … A_{i+1}) \geq P(A_1) + P(A_2) + .. + P(A_{i+1}) – (i+1-1)$$
\begin{align*}
P( A_1 \cap A_2 \cap … A_{i+1}) &=
P( A_1 \cap A_2 \cap … A_{i}) + P(A_{i+1})
– P( \left( A_1 \cap A_2 \cap … A_{i}\right) \cup A_{i+1} ) \\
%P( A_1 \cap A_2 \cap … A_{i+1}) \geq P(A_1) + P(A_2) + .. + P(A_{i+1}) – (i+1-1) \\
\end{align*}
Is my solution correct so far? How do I finish the job?
Best Answer
From your last line, apply $$-P((A_1 \cap \cdots \cap A_i) \cup A_{i+1}) \ge -1$$ and $$P(A_1 \cap A_2 \cap \cdots \cap A_i) \ge P(A_1) + \cdots + P(A_i) - (i-1).$$