there is a step in this proof for the Principle of inclusion-exclusion that is not so clear to me:
\begin{multline*} |A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{1 \leq i \leq n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| \\ + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n|. \end{multline*}
Supposing that $a$ belongs to $r$ original sets, then it is counted $r$ times by the first expression, so it is counted $C(r,1)$ times.
Then my book explains that $a$ is counted $C(r,2)$ times by the second expression, $C(r,3)$ by the third expression and so on up.
Why do we count $a$ $C(r,2)$ times in the second expression?
Thanks for the help
In the second sum, for each $a$ there is one term for each pair of sets both of which contain $a$. There are $C(r,2)$ ways to choose such pairs.
I suggest you draw a Venn diagram and look at all the relevant subsets when $n=3$.