double sum $\sum_{i=1}^N\sum_{j=1}^N \vert i+1-j\vert$

Question

How can I compute the double sum $$S:=\sum_{i=1}^N\sum_{j=1}^N \vert i+1-j\vert \; ?$$

I can divide the sum in $i\ne j$ and for $i=j.$ For $i\ne j$ I can sum as $\sum_{i<j}+\sum_{i>j}.$

So $$S=N+\sum_{j=1}^{N-1}\sum_{i=j+1}^{N}(i+1-j)+\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}(j-i-1)=N+S_1+S_2.$$

I look at $$S_1=\sum_{j=1}^{N-1}\left(1+2+\cdots+(N+1-j)\right)$$ $$=N+2N+\cdots+\sum_{j=1}^{N-1}(N+1-j)$$ $$=N+2N+\cdots+\frac{1}{2}(N^2+N-2)$$ $$=N+2N+\cdots+\frac{N^2}{2}+\frac{N}{2}-1.$$

Not sure how to write it down correct, I find on internet that we need to find the cardinal of the following set $$\{(i,j)\in[1,N]:\; \vert i+1-j\vert =k\}.$$

But not sure how to do so.

Answer 1

It's much simpler than that actually:

Evaluating the inside summation we get:

$$\sum_{i=1}^{N} \Big[|i| + |i-1| + . . . |i-(N-1)|\Big]$$ $$= \frac{N(N+1)}{2} + \Big(\frac{N(N+1)}{2} - 1\Big) + \Big(\frac{N(N+1)}{2} - 2\Big) + . . . + \Big(\frac{N(N+1)}{2} - (N-1)\Big)$$

Can you take it from here?