Trouble reading summation formula

Question

Can somebody help me to understand the syntax of inner summation from this probability equation, because I'm trying to prove it by induction for any $n \ge 2$.

I have no idea how to read it, any tips on reading formulas like this. Thanks

Answer 1

First of all, this summation formula:

$$\sum_{1 \le i < j \le n} P(A_i \cap A_j)$$

means we're looking at all pairs of $(i,j)$ where both numbers are at least $1$ and at most $n$. We also don't care about repeats, so we'll strictly go through only the ones where $i < j$, since $i > j$ would give the same result ($P(A_i \cap A_j)$ or $P(A_j \cap A_i)$).

For example, let's say $n=5$:

$$\begin{align} \sum_{1 \le i < j \le 5} P(A_i \cap A_j) &= & & \\ = P(A_1 \cap A_2) &+ P(A_1 \cap A_3) &+P(A_1 \cap A_4) &+P(A_1 \cap A_5) + \\ &+ P(A_2 \cap A_3) &+ P(A_2 \cap A_4) &+ P(A_2 \cap A_5) + \\ & &+ P(A_3 \cap A_4) &+ P(A_4 \cap A_5) + \\ & & &+ P(A_4 \cap A_5). \ \end{align}$$

Now for the bigger monster:

$$\sum_{1 \le i_1 < i_2 < \dots < i_k \le n} P(A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k})$$

means we're looking at all k-long arrays of numbers $(i_1, i_2, \dots, i_k)$, and we're summing over all possible values of them. This is just an extension of the previous case. We're not interested in repetitions, so we're only looking at the case of $(A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_n})$ where $i_1 < i_2$, $i_2 < i_3$, and so on: $i_{n-1} < i_n$, for example, assuming $n=5, k=4$ the following term will be in our sum: $(A_1 \cap A_3 \cap A_4 \cap A_5)$ (nicely in order), but this term for example won't be in our sum: $(A_3 \cap A_4 \cap A_5 \cap A_1)$, since we would already count this with $(A_1 \cap A_3 \cap A_4 \cap A_5)$.

So for example if we have $n=5, k=4$:

$$\sum_{1 \le i_1 < i_2 < \dots < i_k \le n} P(A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k}) = \\ = P(A_1 \cap A_2 \cap A_3 \cap A_4) + P(A_1 \cap A_2 \cap A_3 \cap A_5) + \\ + P(A_1 \cap A_2 \cap A_4 \cap A_5) + P(A_1 \cap A_3 \cap A_4 \cap A_5) + P(A_2 \cap A_3 \cap A_4 \cap A_5).$$

By the way, for any $n,k \in \Bbb{N}$, if $k \le n$, we'll have $\binom{n}{k}$ terms in the above sum.

Answer 2

This notation is hard to read because the sets $A_*$ are indexed with an indexed subscript. The circled sum is just the sum over the intersections of the sets $A_*$ taken $k$ at a time.

You can rewrite the whole business by starting with a set $\mathbb{A}$ of $n$ sets $A_i$ and writing the terms as sums over intersections of subsets of $\mathbb{A}$ of size $k$.