1
$\begingroup$

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 
$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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