Sum with more indices

Question

I have trouble understanding this way of writing a sum. How can I interpret the sum with indices $1\leq i_1<...< i_r\leq n$ ?$$\left|\bigcup_{i=1}^nA_i\right|=\sum_{r=1}^n(-1)^{r-1}\sum_{1\le i_1<\cdots<i_r\le n}\left|\bigcap_{j=1}^rA_{i_j}\right|$$

Answer 1

This is the inclusion-exclusion principle for the union of $n$ sets.

The inner sum over the $i_j$ indicates choosing all values for such indices satisfying the given inequality. So, for one choice or $r$, we sum the sizes of all $\binom{n}{r}$ intersections of $r$ sets out of the $n$.

The outer sum causes the final result to be the odd-$r$ results minus the even-$r$ results.

Let's consider the $n=2$ case as an example, with contributions from $r=1$ and $r=2$, the latter given a $-$ sign. With $r=1$, the inequality simplifies to $1\le i_1\le2$, so the contribution is $\sum_{i=1}^2|A_i|=|A_1|+|A_2|$ if we rename $i_1$ as $i$ so $i\in\{1,\,2\}$. With $r=2$, the inequality simplifies to $1\le i_1<i_2\le2$, so the contribution is $-\sum_{i<j}|A_i\cap A_j|=-|A_1\cap A_2|$ if we rename $i_1,\,i_2$ as $i,\,j$ respectively so $i=1,\,j=2$. The $n=2$ case is then the famous result$$\left|A_1\cup A_2\right|=|A_1|+|A_2|-|A_1\cap A_2|.$$Similarly, the $n=3$ case is$$\begin{align}|A_1\cup A_2\cup A_3|&=|A_1|+|A_2|+|A_3|\\&-|A_1\cap A_2|-|A_1\cap A_3|-|A_2\cap A_3|\\&+|A_1\cap A_2\cap A_3|.\end{align}$$

Answer 2

At first we look at some special cases, to become more familiar with the notation. Then we look at the general case.

$r=1$: \begin{align*} \sum_{1\leq i_1\leq n} f(i_1)&=\sum_{i_1=1}^n f(i_1)\\ \end{align*}

$r=2$: \begin{align*} \sum_{1\leq i_1<i_2\leq n} f(i_1,i_2)&=\sum_{i_1=1}^{n-1}\,\sum_{i_2=i_1+1}^n f(i_1,i_2)\\ &=\sum_{i_2=2}^n\,\sum_{i_1=1}^{i_2-1}f(i_1,i_2) \end{align*}

$r=3$: \begin{align*} \sum_{1\leq i_1<i_2<i_3\leq n} f(i_1,i_2,i_3)&=\sum_{i_1=1}^{n-2}\,\sum_{i_2=i_1+1}^{n-1}\,\sum_{i_3=i_2+1}^{n} f(i_1,i_2,i_3)\\ &=\sum_{i_3=3}^n\,\sum_{i_2=2}^{i_3-1}\,\sum_{i_1=1}^{i_2-1}f(i_1,i_2,i_3) \end{align*}

General $r$:

\begin{align*} \color{blue}{\sum_{1\leq i_1<i_2<\cdots<i_r\leq n} f(i_1,i_2,\ldots,i_r)}&=\sum_{i_1=1}^{n-(r-1)}\,\sum_{i_2=i_1+1}^{n-(r-2)}\cdots\sum_{i_r=i_{r-1}+1}^{n} f(i_1,i_2,\ldots,i_r)\\ &=\sum_{i_r=r}^n\,\sum_{i_{r-1}=r-1}^{i_r-1}\cdots\sum_{i_1=1}^{i_2-1}f(i_1,i_2,\ldots,i_r) \end{align*}