Let $(\Omega,\mathcal F, P)$ be a probability space and let $A_1,A_2,...,A_n$ be events in $\mathcal F$.

Prove the following inclusion-exclusion formula

$P(\bigcup_{i=1}^nA_i)=\sum_{k=1}^n$ $\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)$

I am trying to prove this formula by induction; for $n=2$, let $A, B$ be two events in $\mathcal F$. We can write $A=(A \setminus B) \cup (A\cap B)$, $B=(B \setminus A) \cup (A\cap B)$, since these are disjoint unions, then

$P(A)=P(A \setminus B)+P(A\cap B)$ and $P(B)=P(B \setminus A)+P(A\cap B)$.

Now, $A \cup B$ can be expressed as $A \cup B= (A\setminus B) \cup (A \cap B) \cup (B \setminus A)$, which it's also union of disjoint sets, so

$P(A \cup B)=P(A \setminus B)+P(A\cap B)+P(B \setminus A)=P(A)+P(B)-P(A \cap B)$.

This proves that for $n=2$, the formula is correct.

Now, I want to show that the formula is true for $n \implies$ the formula is satisfied for $n+1$, I got stuck at this point, maybe I could express $P(\cup_{i=1}^{n+1} A_i)=P((\cup_{i=1}^n A_i \setminus A_{n+1}) \cup A_{n+1})=P(\cup_{i=1}^n A_i \setminus A_{n+1})+P(A_{n+1})$ (1)

I can use the inductive hypothesis on the term $P(\cup_{i=1}^n A_i \setminus A_{n+1})$, so $P(\cup_{i=1}^n (A_i \setminus A_{n+1}))=\sum_{k=1}^n$ $\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} (A_i\setminus A_{n+1}))$

Expression (1) becomes $\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} (A_i\setminus A_{n+1})) +P(A_{n+1})$

I don't know to to take this expression to the one I want, which is

$\sum_{k=1}^{n+1}$ $\sum_{\mathcal J \subset \{1,...,n+1\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)$

I would like to know how to continue this part of the exercise.


For an alternative to Hamou's approach—and one that's more similar to your initial idea—you can do the following: observe that $P(A\setminus B)=P(A)-P(A\cap B).$ So $$ \begin{aligned} P\left(\bigcup_{i=1}^{n+1}A_i\right)&=P\left(\bigcup_{i=1}^n A_i\right)+P\left(A_{n+1}\setminus\bigcup_{i=1}^n A_i\right)\\ &=P\left(\bigcup_{i=1}^n A_i\right)+P(A_{n+1})-P\left(\bigcup_{i=1}^n (A_i\cap A_{n+1})\right). \end{aligned} $$ Now apply the induction hypothesis to both unions in this last expression.

  • $\begingroup$ Thanks very much for your answer. I think I almost got it except from one minus sign. The last expression you wrote, using the IH, is equal to $\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)+P(A_{n+1})-\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i \cap A_{n+1})$. $\endgroup$ – user100106 Aug 24 '14 at 18:53
  • $\begingroup$ On the other hand, the expression $\sum_{\mathcal J \subset \{1,...,n+1\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)$ can be separated in two (actually, three) terms: 1) all possible intersections between sets except $A_{n+1}$, and all combinations of intersections where $A_{n+1}$ is intersected. This is $\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)+\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i \cap A_{n+1})+P(A_{n+1}).$ Why are they almost the same except for the minus? $\endgroup$ – user100106 Aug 24 '14 at 19:00
  • 2
    $\begingroup$ Those intersections that contain $A_{n+1}$ in your last expression are of size $k+1,$ not size $k.$ So instead of $(-1)^{k+1}$ you should have $(-1)^{k+2}.$ $\endgroup$ – Will Orrick Aug 24 '14 at 19:28
  • $\begingroup$ Can you tell me why doesn't $A_{n+1}$ stop us from applying the induction ? $\endgroup$ – James Groon Oct 14 '17 at 17:59
  • 1
    $\begingroup$ @JamesGroon the induction is on the number of terms in the union, which is $n$ for both unions. Under the induction hypothesis, the principle of inclusion-exclusion holds for unions of $n$ terms. By grouping terms, and simplifying some of them, the principle can be deduced for unions of $n+1$ terms. $\endgroup$ – Will Orrick Oct 14 '17 at 18:50

Hint: For $n\Rightarrow n+1$: $A_1,\ldots,A_n,A_{n+1}$, take $B_1=A_1,\ldots,A_{n-1}=B_{n-1},B_n=A_n\cup A_{n+1}$ and apply the inductive hypothesis to $B_1,\ldots,B_n$.

  • $\begingroup$ I could arrive to $P(\cup_{i=1}^n B_i)=\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} B_i)$, this term equals to $\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} B_i)+\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k-1} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} B_i \cap B_n)=\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)+\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k-1} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i \cap (A_n \cup A_{n+1}))$ $\endgroup$ – user100106 Aug 23 '14 at 21:22
  • $\begingroup$ Could you help me to continue? Btw, thanks for the suggestion. $\endgroup$ – user100106 Aug 23 '14 at 21:22
  • 1
    $\begingroup$ For the second term $\cap_{i\in J}A_i\cap(A_n\cup A_{n+1})=\left(\cap_{j\in J}A_i\cap A_n\right)\cup \left(\cap_{j\in J}A_i\cap A_{n+1}\right)$ $\endgroup$ – Hamou Aug 23 '14 at 21:27
  • $\begingroup$ Sorry I keep asking, I am having problems reducing this expression to the one I want:$\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)+\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k-1} (-1)^k(P(\bigcap_{i \in \mathcal J} A_i \cap A_n)+ P(\bigcap_{i \in \mathcal J} A_i \cap A_{n+1})-P(\bigcap_{i \in \mathcal J} A_i \cap A_n \cap A_{n+1}))$ $\endgroup$ – user100106 Aug 23 '14 at 21:39
  • $\begingroup$ What is the number of part intersection here $\cap_{j\in J}A_i\cap A_n$ and here $\cap_{j\in J}A_i\cap A_{n+1}$ and here $\cap_{j\in J}A_i\cap A_n\cap A_{n+1}$? add its in the term corresponding with the cardinal. $\endgroup$ – Hamou Aug 23 '14 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.