# How to read the notations in the proof of the inclusion-exclusion principle?

This question is a follow up to this question.

How do I create a sequence from this formula?

$\sum\limits_{i=1}^{n} P(A_i) - \sum\limits_{1\le i < j \le n-1}P(A_i \cap A_j) + \dots + (-1)^n P(A_1 \cap A_2 \cap \dots \cap A_{n-1}) - \left[ \sum\limits_{i=1}^{n-1}P(A_i \cap A_n) - \sum\limits_{1\leq i < j \leq n-1}^{n-1}P(A_i \cap A_j \cap A_n) + \dots + (-1)^nP(A_i \cap A_2 \cap \dots \cap A_{n-1}\cap A_n)\right]$

My confusion is in interpreting $(-1)^n P(A_1 \cap A_2 \cap \dots \cap A_{n-1})$ and $(-1)^nP(A_i \cap A_2 \cap \dots \cap A_{n-1}\cap A_n)$.

Take $(-1)^n P(A_1 \cap A_2 \cap \dots \cap A_{n-1}$ as an example. I don't know where $n$ should begin. I thought it is $1$ but if $n=1$ then the first term, $\sum\limits_{i=1}^{n}P(A_i)$, should have a negative sign because $(-1)^1=-1$. Since this is not the case, it must mean that $n$ starts from 2. But this not mentioned anywhere in the theorem.

Lastly, based on Antoine's answer, how do I formally complete the proof? I can see that the missing terms in the first line can be found in the second line and that the final term in the second line will always be the last term as per the theorem. But I don't know the sequence of steps to write so that the end of this proof is a formula as per the theorem.

• Note for $n=1$ you have $P(\emptyset) = 0$ so all is fine. – AlexR Sep 22 '13 at 6:53
• @AlexR I thought if $n=1$, then I should end up with $P(A_1)$. If that is not the case, how do I get $P(A_1)$ from this formula? – mauna Sep 22 '13 at 7:23
• Notice how this is $$P(A_1 \cap \ldots \cap A_{n-1})$$ And $A_0$ isn't really defined at all; you get $P(A_1)$ with $n=2$ – AlexR Sep 22 '13 at 8:02
• @AlexR Thanks. I understand it now. But I still don't know how to formally complete the proof. Would you be able to help? – mauna Sep 22 '13 at 10:10
• Well, just take the $(-1)$ in front of the brackets and multiply it. notice $i\leq n-1 \Rightarrow i<n$ to complete. – AlexR Sep 22 '13 at 13:00

$$\sum\limits_{i=1}^{n} P(A_i) - \sum\limits_{1\le i < j \le n-1}P(A_i \cap A_j) + \dots + (-1)^n P(A_1 \cap A_2 \cap \dots \cap A_{n-1}) - \left[ \sum\limits_{i=1}^{n-1}P(A_i \cap A_n) - \sum\limits_{1\leq i < j \leq n-1}^{n-1}P(A_i \cap A_j \cap A_n) + \dots + (-1)^nP(A_i \cap A_2 \cap \dots \cap A_{n-1}\cap A_n)\right] = \sum_{k=1}^n \sum_{|\alpha| = k} (-1)^{k + 1} P\left(\bigcap_{i=1}^{|\alpha|}A_{\alpha_i}\right)$$ Where $\alpha \in ([1,n]\cap\mathbb N)^{k}$ is a multiindex with $i < j \Leftrightarrow \alpha_i < \alpha_j$ and $|\alpha|=k$ is its length. Just try to formalize it a bit. You'll notice that for example $$\sum_{1\leq i<j\leq n-1} P(A_i\cap A_j) + \sum_{i=1}^{n-1} P(A_i \cap A_n) = \sum_{1\leq i<j \leq n} P(A_i \cap A_j) = \sum_{|\alpha| = 2} P(A_{\alpha_1} \cap A_{\alpha_2})$$
• The notation $\alpha \in [1,n]_{\mathbb N}^{k}$ is new to me. Is there some online site I can read up to better understand it (along with examples)? – mauna Sep 23 '13 at 12:08
• $[a,b]_{\mathbb N}$ is a short version of $$[a,b] \cap \mathbb N$$ The exponent $k$ is just the $k$-dimensional carthesian product of the set. $\alpha$ is a vector of length $k$ containing strictly increasing natural numbers between $1$ and $n$. @mauna I also added a reference in the post (this). Does it help? – AlexR Sep 23 '13 at 12:11