# Double Summation: why summation can be split like this?

## Problem

I don't know how to get from (1) to (2), more specifically: I don't know why $$\frac{1}{N^2}$$ can become $$\frac{1}{N}$$ after the split? Is there any definition or rule that tells us we can do such a thing?

\begin{align*} \frac{1}{N^2} \sum^{N}_{i,j=1}(x_i - x_j)^2 &= \frac{1}{N^2}\sum_{i,j=1}^{N}x_i^2 + x_j^2 - 2x_{i}x_{j} \tag{1} \\\\ &= \frac{1}{N}\sum_{i=1}^{N}x_i^2 + \frac{1}{N}\sum_{j=1}^{N}x_j^2 - \frac{2}{N^2}\sum_{i=1}^{N}\sum_{j=1}^{N}x_ix_j \tag{2} \end{align*}

• You have a double sum over $1 \leq i,j \leq N.$ Since the $x_i^2$'s don't depend on $j,$ the summation over $j$ turns into a factor $N$ which cancels one of the $N$'s in $1/N^2.$ The same goes for the sum of the $x_j^2$'s, this time with the roles of $i$ and $j$ reversed. Note that the last sum cannot be simplified like this, so the factor $1/N^2$ stays like that.
– Edd
Commented Aug 13, 2023 at 10:31
• Double sum means $\sum_{i,j=1} = \sum_{i}\sum_{j}$ ? Commented Aug 13, 2023 at 10:33
• Yes, what else? Commented Aug 13, 2023 at 10:33
• @Yiffany If the general term of an indexed sum of $N$ terms doesn't depend on the index, the summation turns into adding the same term $N$ times, so it becomes $N$ times the term being repeated: $$\sum_{i,j=1}^N x_i^2 = \sum_{j=1}^N \left( \sum_{i=1}^N x_i^2 \right) = N \sum_{i = 1}^N x_i^2.$$
– Edd
Commented Aug 13, 2023 at 11:13

Let's separately take a look at the sum of the form $$\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}z_i$$, where summand doesn't depend on the one of indexes of the summation. $$\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}z_i=\sum\limits_{i=1}^{N}\underbrace{\left(\sum\limits_{j=1}^{N}z_i\right)}_{\text{we can put out z_i because it does not depend on j}}=\\=\sum\limits_{i=1}^{N}\left(z_i\sum\limits_{j=1}^{N}1 \right)=\sum\limits_{i=1}^{N}\left(z_i\left(\underbrace{1+1+....+1}_{N \text{ times}}\right)\right) = \sum\limits_{i=1}^{N}z_i \cdot N =\\ = N\sum\limits_{i=1}^{N}z_i$$

Now we just need to use this trick two times.

$$\frac{1}{N^2} \sum^{N}_{i,j=1}(x_i - x_j)^2 = \frac{1}{N^2}\sum_{i,j=1}^{N}\left(x_i^2 + x_j^2 - 2x_{i}x_{j}\right) = \\ = \frac{1}{N^2}\sum_{i=1}^{N}\sum_{j=1}^{N}\left(\underbrace{x_i^2}_{\text{does not depend on j}} + \underbrace{x_j^2}_{\text{does not depend on i}} - 2x_{i}x_{j}\right)= \\= \frac{1}{N^2}\sum_{i=1}^{N}\sum_{j=1}^{N}x_i^2 + \frac{1}{N^2}\sum_{j=1}^{N}\sum_{i=1}^{N}x_j^2 - \frac{2}{N^2}\sum_{i=1}^{N}\sum_{j=1}^{N}x_ix_j = \\ = \frac{1}{N^2}\sum_{i=1}^{N}Nx_i^2+\frac{1}{N^2}\sum_{j=1}^{N}Nx_j^2-\frac{2}{N^2}\sum_{i=1}^{N}\sum_{j=1}^{N}x_ix_j = \\ = \frac{1}{N}\sum_{i=1}^{N}x_i^2 + \frac{1}{N}\sum_{j=1}^{N}x_j^2 - \frac{2}{N^2}\sum_{i=1}^{N}\sum_{j=1}^{N}x_ix_j$$

Here we have finite sums and can conveniently apply commutative, associative and distributive laws with respect to addition and multiplication.

We obtain \begin{align*} \color{blue}{\frac{1}{N^2}}&\color{blue}{\sum_{i,j=1}^{n}\left(x_i-x_j\right)^2} =\frac{1}{N^2}\sum_{i,j=1}^n\left(x_i^2+x_j^2-2x_ix_j\right)\tag{1}\\ &=\frac{1}{N^2}\sum_{i=1}^n\sum_{j=1}^nx_i^2+\frac{1}{N^2}\sum_{i=1}^N\sum_{j=1}^Nx_j^2 -\frac{2}{N^2}\sum_{i=1}^N\sum_{j=1}^Nx_ix_j\tag{2}\\ &=\frac{1}{N^2}\left(\sum_{i=1}^Nx_i^2\right)\left(\sum_{j=1}^n1\right) +\frac{1}{N^2}\left(\sum_{i=1}^N1\right)\left(\sum_{j=1}^Nx_j^2\right)\tag{3}\\ &\qquad-\frac{2}{N^2}\sum_{i=1}^N\sum_{j=1}^Nx_ix_j\\ &=\frac{1}{N}\sum_{i=1}^Nx_i^2+\frac{1}{N}\sum_{j=1}^Nx_j^2-\frac{2}{N^2}\sum_{i,j=1}^Nx_ix_j\tag{4}\\ &\,\,\color{blue}{=\frac{2}{N}\sum_{i=1}^Nx_i^2-\frac{2}{N^2}\sum_{i,j=1}^Nx_ix_j}\tag{5} \end{align*}

Comment:

• In (1) we add parentheses, since the terms $$x_j^2$$ and $$-2x_ix_j$$ need to be tied to the summation symbol. Here $$x_i$$ and $$x_j$$ are so-called bound variables.

• In (2) we need for convenience of easier rearrangements the less compact notation $$\sum_{i}\sum_{j}$$ which is the same as $$\sum_{i,j}$$. We also split the sums which is just an application of associative and distributive laws.

• In (3) we factor out $$x_i^2$$ from the innermost sum of the first double sum and again apply associative and distributive laws during rearrangements.

• In (4) we use $$\sum_{i=1}^N1=\sum_{j=1}^N1=N$$.

• In (5) we collect like sums since \begin{align*} \sum_{i=1}^Nx_i^2=x_1^2+x_2^2+\cdots+x_N^2=\sum_{j=1}^Nx_j^2. \end{align*}