# Double summation with dependent variables

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?

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_{ij}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 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$$.