How can I write this as a double sum?

Question

I'm confused about this notation, can someone please explain how I can write

$2 \sum_{1\leq j < k \leq N} P(F_j F_k)$ as a double sum. Would it be $\sum_{j=1}^k \sum_{k=n}^N P(F_j F_k)$?

Also I am just confused about what a double sum would actually mean, I understand that you would sum over the values twice but can someone please explain more in detail? Thank you

Answer 1

A double sum is a sum of the form $$\sum_{j=a}^b \sum_{k=c(j)}^{d(j)} f(j,k) = \sum_{j=a}^b \left(\sum_{k=c(j)}^{d(j)} f(j,k)\right)$$ I used the notation $c(j),d(j)$ because $c$ and $d$ may very well depend on $j$, but they don't have to.

There are more ways you can approach this.

1. We want one variable, say $j$, to be independent, and let it independently take all the values it can possibly have that satisfy the condition $1\le j < k \le N$. We will then adjust $k$ so that this condition is actually met.
   Therefore, let $j$ vary across all values that it can possibly have. These are $1\le j \le N-1$, hence the $\sum_{j=1}^{N-1}$ symbol. Then, let $k$ take all values such that the condition $j < k \le N$. A different way to write this inequality is $j+1 \le k \le N$. Hence, your sum is equal to $$2\sum_{j=1}^{N-1} \sum_{k=j+1}^N P(F_jF_k)$$ To expand this sum, first write out all terms of the inner sum, and then add them up according to the outer sum, like $$2\sum_{j=1}^{N-1} (P(F_jF_{j+1})+P(F_jF_{j+2})+...+P(F_jF_N)) =$$ $$= 2[(P(F_1F_2)+P(F_1F_3)+...+P(F_1F_N)) +$$ $$+(P(F_2F_3)+P(F_2F_4)+...+P(F_2F_N))+...+$$ $$+P(F_{N-1}F_N)]$$ Notice that each successive term of the outer sum has less and less terms of the inner sum (the last one has only one term).

2. Let $k$ vary across all values that it can possibly have. These are $2\le k \le N$. Then, let $j$ take all values such that the condition $1\le j < k$ is met. A different way to write this inequality is $1 \le j \le k-1$. Hence, your sum is equal to $$2\sum_{k=2}^{N} \sum_{j=1}^{k-1} P(F_jF_k)$$

The difference between these two approaches is which variable you assign "independence" to.

Answer 2

$$\sum_{j=1}^{N-1} \sum_{k=j+1}^N P(F_j,F_k)$$

Answer 3

Let's start with something more general:
Assume, that for some finite set $I$, you have a sum $$ \sum_{l \in I} s_i $$ Now, the summands correspond to the elements in $I$. If, for some set $J$, we have a bijection

$$ I \overset{\sigma}{\longrightarrow} \bigcup_{j \in J}I_j =: Y $$ where $I_j \cap I_i = \emptyset$ for $i\neq j$, then

$$ \sum_{i\in I} s_i = \sum_{y \in Y} s_{\sigma^{-1}(y)} = \sum_{y \in \bigcup_{j \in J}I_j} s_{\sigma^{-1}(y)} = \sum_{j \in J}\sum_{y \in I_j} s_{\sigma^{-1}(y)} $$ The first equation holds because $\sigma$ is a permutation and addition is commutative. The second equation is trivial and the third equation uses that the union is disjoint, as mentioned above.

So, any bijection $\sigma$ into a disjoint union as mentioned above will give you a representation as a double sum. You could of course proceed inductively, to get triple, quadruple sums et cetera.
The double sum can hence be understood as a specific grouping of summands/a partition of the index set.

Concerning your special case:
Defining $I:=\left\{\left(j,k\right);\,1\leq j < k \leq N\right\}$, you can write $$ I = \bigcup_{1 \leq j < N} \underbrace{\left\{(j,k);\, j < k \leq N\right\}}_{:= I_j} $$ and the union is disjoint. Taking $\sigma$ as the identity, and using the above, we get $$ \begin{eqnarray} & 2 \sum_{(j,k) \in I} P(F_j F_k) = 2 \sum_{(j,k) \in \bigcup_{1 \leq j < N} I_j} P(F_j F_k) = 2 \sum_{1 \leq j < N} \sum_{(j,k) \in I_j} P(F_j F_k) = \\ & 2 \sum_{1 \leq j < N}\; \sum_{(j,k) \in \left\{(j,m);\, j < m \leq N \right\}} P(F_j F_k) = 2 \sum_{1 \leq j < N} \sum_{j < k \leq N} P(F_j F_k) \\ \end{eqnarray} $$

where in the last equation, we used that the sets $ \left\{(j,m);\, j < m \leq N\right\} $ and $ \left\{m;\, j < m \leq N\right\} $ are bijective/have the same number of elements. There is some subtle formal detail involved in this last equation:

We are basically applying what we used before - $\sum_{i\in I} s_i = \sum_{y \in Y} s_{\sigma_j^{-1}(y)}$ - to the inner sum, where for each $j$, $\sigma_j: \left\{(j,m);\, j < m \leq N\right\} \longrightarrow \left\{m;\, j < m \leq N\right\},\; (j,m) \mapsto m$ is the projection to the second component and $\sigma_j^{-1}$ is the function that maps $m \mapsto (j,m)$.

Explicitly, $$ \begin{array} & 2 \sum_{1 \leq j < N}\; \sum_{(j,k) \in \left\{(j,m);\, j < m \leq N \right\}} P(F_j F_k) = 2 \sum_{1 \leq j < N}\; \sum_{(j,k) \in \left\{(j,m);\, j < m \leq N \right\}} P(F_j F_{\sigma_j(j,k)}) = \\ 2 \sum_{1 \leq j < N} \sum_{j < k \leq N} P(F_j F_{\sigma_j(\sigma_j^{-1}(k))}) = 2 \sum_{1 \leq j < N} \sum_{j < k \leq N} P(F_j F_k) \\ \end{array} $$