MHB Understanding the Inclusion-Exclusion Principle for Multiple Events

[Jameson]

The inclusion-exclusion principle shows that for two events $P[A \cup B]=P[A]+P-P[A \cap B]$ and for three events $P[A \cup B \cup C] = P[A] + P + P[C] - P[A \cap B] - P[A \cap C] - P[B \cap C] + P[A \cap B \cap C]$.

Using these as a guideline what is $P[A \cup B \cup C \cup D]$? In general, how many terms will be in $$P\left[ \bigcup_{i=1}^{n} A_i \right]$$?
--------------------

 

[Jameson]

Congratulations to the following members for their correct solutions:

1) Ackbach

Solution (from Ackbach):

Spoiler

The guideline yields the pattern of having to subtract, then add, then subtract, so as not to count things more than once. Based on that, we have that
\begin{align*}
P(A \cup B \cup C \cup D)&=P(A)+P(B)+P(C)+P(D) \\
& \quad -P(A \cap B)-P(A \cap C)-P(A \cap D)-P(B \cap C)-P(B \cap D)-P(C \cap D) \\
& \quad +P(A \cap B \cap C)+P(A \cap B \cap D)+P(A \cap C \cap D)+P(B \cap C \cap D) \\
& \quad -P(A \cap B \cap C \cap D).
\end{align*}
The pattern here for the number of terms is that
$$P \left[ \bigcup_{j=1}^{n}A_{j} \right]$$
has $2^{n}-1$ terms. Technically, it has $2^{n}$ terms, one for each possible subset; but $P[ \varnothing]=0$, so it'll never contribute to the sum.

Alternate solution:

Spoiler

We can see that $P[A \cup B \cup C \cup D]$ has 4 terms, then 3, then 3 then 1 if you partition the terms into the amount of intersections. Written another way, it has $$\binom{4}{1}+\binom{4}{2}+\binom{4}{3}+\binom{4}{4}$$ terms. If we generalize this we can see that the number of terms in $$P \left[ \bigcup_{i=1}^{n}A_{i} \right]$$ is $$\sum_{i=1}^{n}\binom{n}{i}$$.