1

So I was participating in this contest and now that it's over I was checking the editorial for the author solution. Basically the solution was deriving a single summation from a double summation in order to have a more efficient solution ..

But I couldn't understand one step in the derivation bellow .. I've highlighted the unclear step bellow .. I've tried to derive it but I could not .. Any hints about this are appreciated ..

$\sum_{i=1}^{k-1} \sum_{j=1}^{k-1} (b_i - b_j)^2$

$\implies \sum_{i=1}^{k-1} \sum_{j=1}^{k-1} (b_i^2 + b_j^2 - 2 . b_i . b_j)$

$\implies 2.k .\sum_{i=1}^{k-1} (b_i^2) - 2 . \sum_{i=1}^{k-1} \sum_{j=1}^{k-1} b_i . b_j$

$ \implies 2.k .\sum_{i=1}^{k-1} (b_i)^2 - 2 . (\sum_{i=1}^{k-1} b_i)^2 $

                        ^ this step
motatoes
  • 113

2 Answers2

2

$$\sum_i (\sum_j b_i \cdot b_j) = \sum_i (b_i \cdot \sum_j b_j) = (\sum_j b_j) \cdot (\sum_i b_i)$$

Karolis Juodelė
  • 9,702
  • 1
  • 25
  • 39
1

Write it in a square. We show that $\sum_{i=1}^3 \sum_{j=1}^3 b_i b_j = \sum_{i=1}^3 b_i \sum_{j=1}^3 b_j$, relabelling $b_1, b_2, b_3 = a,b,c$.

 ––a–– ––b–– ––c––
|
a  a*a  a*b   a*c
|
|
b  b*a  b*b   b*c
|
|
c  c*a  c*b   c*c
|

The area of the large outer square is the RHS; the sum of each of the smaller areas (for time's sake, I haven't drawn in the dividing lines for the nine smaller rectangles of area $a^2, ab, ac, \dots$) makes up the left-hand side. Each combination of $b_i b_j$ (as $i, j$ range from $1$ to $3$ independently) shows up as exactly one of the little rectangles.

Patrick Stevens
  • 36,135