0
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Where does $n$ come from? $\endgroup$ Mar 3 '19 at 23:47
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Mar 4 '19 at 0:45
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – user477465
    Mar 4 '19 at 4:31
  • $\begingroup$ also, why do you initially take j to be $1 \leq j \leq N-1$ $\endgroup$
    – user477465
    Mar 4 '19 at 4:33
  • $\begingroup$ 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? $\endgroup$
    – user477465
    Mar 4 '19 at 4:34
  • $\begingroup$ @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. $\endgroup$ Mar 4 '19 at 5:01
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.