Currently i have taken part in a coding contest where i was asked this question https://atcoder.jp/contests/abc186/tasks/abc186_d. In the editorial solution they have given something like this:
Here especially in the second last step how the outer summation changes from $\sum_{i=1}^{N-1}$ to $\sum_{i=1}^N$ and the inner changes from $\sum_{j=i+1}^N$ to $\sum_{j=1}^N$?
I am not able understand this double summation variable change. Can someone please help me with it?
Best Answer
For brevity write $x_{ij}:=|A_i-A_j|$. Work backwards. The final quantity is $$\frac12\sum_{i=1}^N\sum_{j=1}^N x_{ij}$$ which is a sum over all pairs $(i,j)$ where $i$ and $j$ each run from $1$ to $N$. The trick is to observe that this sum can be broken into three pieces: $$\frac12\sum_{i<j} x_{ij} + \frac12\sum_{i=j}x_{ij} + \frac12\sum_{i>j}x_{ij}.$$ By symmetry, the first and last sums are equal to each other (since $x_{ij}=x_{ji}$). Meanwhile, the middle sum equals zero (since $x_{ii}=0$). So now the sum is $$ \sum_{i<j}x_{ij} $$ which is the first quantity. If you plot in the $i,j$-plane all possible values for the pairs $(i,j)$ you'll get a square array of dots. The above maneuver corresponds to splitting the square into a diagonal (where $i=j$), and two triangles with the same $x_{ij}$ values.
EDIT: To go from the second-last line to the last line, the steps in detail are: $$\begin{aligned} &\frac12\sum_{i=1}^{N-1}\sum_{j=i+1}^N (x_{ij} + x_{ji})\\ \stackrel{(1)}=&\frac12\sum_{i=1}^{N-1}\sum_{j=i+1}^N x_{ij} + \frac12\sum_{i=1}^{N-1}\sum_{j=i+1}^Nx_{ji}\\ \stackrel{(2)}=&\frac12\sum_{i=1}^{N-1}\sum_{j=i+1}^N x_{ij} + \frac12\sum_{j=1}^{N-1}\sum_{i=j+1}^Nx_{ij}\\ \stackrel{(3)}=&\frac12\sum_{i=1}^{N-1}\sum_{j=i+1}^N x_{ij}+\frac12\sum_{i=1}^N x_{ii} + \frac12\sum_{j=1}^{N-1}\sum_{i=j+1}^Nx_{ij}\\ \stackrel{(4)}=&\frac12\sum_{i=1}^N\sum_{j=1}^N x_{ij} \end{aligned} $$ In step (1) we split the sum into two pieces. In step (2) we reindex the second sum by relabeling index $i$ as $j$ and index $j$ as $i$. In step (3) we are adding zero. In step (4) we observe that the three summations cover all possible pairs of $(i,j)$ from $1$ to $N$.