$\sum_{i=1}^n\sum_{j=1}^n{|i-j|}$

Question

I was given this summation :

$$\displaystyle\sum_{i=1}^n\sum_{j=1}^n{|i-j|}$$

And my idea was to use the fact that:

$\displaystyle\sum_{j=1}^n{|i-j|}$=$\displaystyle\sum_{j=1}^i{(i-j)}$+$\displaystyle\sum_{j=i+1}^n{(j-i)}$

Any other solutions ?

Answer 1

Since you asked for ideas, I'll give you a hint-

Consider a table with all the values of $i$ from $1$ to $n$ written on top, and all the values of $j$ from $1$ to $n$ written at the left. And, the entries of the table are the corresponding values of $|i-j|$.

The key thing to notice is

All the main diagonal elements are $0$ and the table is symmetric along the diagonal. So, the top and the bottom triangles are the same

The rest is finding a nice form for carrying out the required computation.

In case you're confused with the description of the table, the table for the case $n=4$ for example, would look like \begin{array}{|c|c|c|c|c|} \hline \text{} & i=1 & i=2 & i=3 & i=4\\ \hline j=1 & 0 & 1 & 2 & 3 \\ \hline j=2 & 1 & 0 & 1 & 2 \\ \hline j=3 & 2 & 1 & 0 & 1 \\ \hline j=4 & 3 & 2 & 1 & 0 \\ \hline \end{array}

Hope that helps.