Algebraic identity I cannot solve

Question

$$ \sum_{i<j}\sum_{j=1}^N(y_i-y_j)^2= N \sum_{j=1}^N(y_i-\bar{y})^2 $$ Where, $\bar{y}$ is the average.

This is what I did: $$ \sum_{i<j}\sum_{j=1}^N(y_i-y_j)^2\\=\sum_{i<j}\sum_{j=1}^N((y_i-\bar{y})-(y_j-\bar{y}))^2 \\= \sum_{i<j}\sum_{j=1}^N(y_i-\bar{y})^2+\sum_{i<j}\sum_{j=1}^N(y_j-\bar{y})^2-2\sum_{i<j}\sum_{j=1}^N(y_i-\bar{y})(y_j-\bar{y}) $$

Now, the third term is zero as $(y_i-\bar{y})$ can be taken outside of the inner summation. I tried to simplify further but, it did not work out finally. Any help is appreciated.

Answer 1

$$ \sum_{i<j}\sum_{j=1}^N(y_i-y_j)^2= N \sum_{j=1}^N(y_i-\bar{y})^2 $$ Where, $\bar{y}$ is the average.

This is what I think might work given a clue from @angryavian: $$ \sum_{i<j}\sum_{j=1}^N(y_i-y_j)^2\\=\frac12\sum_{i=1}^N\sum_{j=1}^N((y_i-\bar{y})-(y_j-\bar{y}))^2 \\= \frac12\sum_{i=1}^N\sum_{j=1}^N(y_i-\bar{y})^2+\frac12\sum_{i=1}^N\sum_{j=1}^N(y_j-\bar{y})^2-\sum_{i=1}^N\sum_{j=1}^N(y_i-\bar{y})(y_j-\bar{y})\\=\sum_{i=1}^N\sum_{j=1}^N(y_i-\bar{y})^2\\=N \sum_{j=1}^N(y_i-\bar{y})^2 $$ Note, the third term from the expansion of the square is zero as $(y_i-\bar{y})$ can be taken outside of the inner summation. What say? The second step follows from symmetry.

Answer 2

This is a classical identity regarding the variance. Let $Y,Z$ be two i.i.d. variables distributed uniformly over $y_1,\ldots,y_N$. The right-hand side of the identity is $$ N^2 \mathbb{E}[(Y-\mathbb{E}Y)^2] = N^2 \mathbb{V}[Y]. $$ For the left-hand side of the identity, notice that if we replace the first sum by a sum over all pairs $i,j$ then we double the resulting value. Undoing this process, we deduce that the left-hand side is $$ \frac{1}{2} N^2 \mathbb{E}[(Y-Z)^2]. $$ Therefore the identity is equivalent to $$ \mathbb{E}[(Y-Z)^2] = 2\mathbb{V}[Y]. $$ To prove this, the trick is to replace $Y-Z$ with $(Y-\mathbb{E}Y)-(Z-\mathbb{E}Z)$: $$ \begin{align*} \mathbb{E}[(Y-Z)^2] &= \mathbb{E}[((Y-\mathbb{E}Y)-(Z-\mathbb{E}Z))^2] \\ &= \mathbb{E}[(Y-\mathbb{E}Y)^2] + \mathbb{E}[(Z-\mathbb{E}Z)^2] - 2\mathbb{E}[(Y-\mathbb{E}Y)(Z-\mathbb{E}Z)] \\ &= \mathbb{V}[Y] + \mathbb{V}[Z] - 2\mathbb{E}[Y-\mathbb{E}Y]\mathbb{E}[Z-\mathbb{E}Z] \\ &= 2\mathbb{V}[Y] - 2\cdot 0\cdot 0 \\ &= 2\mathbb{V}[Y]. \end{align*} $$