# How can I write this as a double sum?

$$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

• Where does $n$ come from? Mar 3 '19 at 23:47
• Does $P(F_j F_k)$ have any special meaning? Generally Readers can only assume it is a term that depends on $j,k$ in a symmetric fashion, i.e. because $F_jF_k=F_kF_j$. But already in the first summation you've restricted the terms so that $j\lt k$, eliminating any cases $j=k$ and raising a suspicion about why the factor $2$ appears in front of that summation, but not in front of your attempt to rewrite it as a double sum. Mar 4 '19 at 0:45

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.

• thank you! i have a really stupid question but how come certain double sums have a 2 next to it and other double sums do not? Mar 4 '19 at 4:31
• also, why do you initially take j to be $1 \leq j \leq N-1$ Mar 4 '19 at 4:33
• And just one more question (sorry!), what exactly does this double sum expand to? like if i had actual numbers/values, then how would this expand? Mar 4 '19 at 4:34
• @user477465 The 2 is there because your starting sum is multiplied by 2. Maybe the 2 was a typo on your part? As for why I take $1\le j \le N-1$... If you have $1\le j < k \le N$ in the sum, this means that the sum contains all possible combinations of $j$ and $k$ that satisfy this. You can see that $j$ can take the smallest value 1, and $j$ can take the value $N-1$, but it can't take $N$ because then $k$ would have to be $>N$. Of course, $N=1$ is a special case, where no $j,k$ satisfy the condition of the sum, hence the sum is 0. Also, see my edit to the answer. Mar 4 '19 at 5:01

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

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.

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}$$