3
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Edd
    Commented Aug 13, 2023 at 10:31
  • $\begingroup$ Double sum means $\sum_{i,j=1} = \sum_{i}\sum_{j}$ ? $\endgroup$
    – Yiffany
    Commented Aug 13, 2023 at 10:33
  • $\begingroup$ Yes, what else? $\endgroup$
    – trula
    Commented Aug 13, 2023 at 10:33
  • 1
    $\begingroup$ @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.$$ $\endgroup$
    – Edd
    Commented Aug 13, 2023 at 11:13

2 Answers 2

2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .