Proof of an identity with a nested summation

Question

Suppose for all $n>1$ the following equation is true: $$\sum_{i=1}^{n}\sum_{j=1}^{n} |i-j|=\frac{n\left(n^{2}-1 \right)}{3}$$ Can I prove this by induction? Is it possible to combine the two summations into one?

Answer 1

Let us assume that the result is true for $n$, so $\displaystyle \sum_{i=1}^{n}\sum_{j=1}^{n} |i-j| = \frac{n(n^{2} - 1)}{3}$.

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

So, the result is also true for $n+1$. By induction, rest follows...

Answer 2

For what its worth, my first try here would not be induction.

Tools
T-1 $~: ~\displaystyle \sum_{s=1}^t s = \frac{t(t+1)}{2}.$
T-2 $~: ~\displaystyle \sum_{s=1}^t s^2 = \frac{t(t+1)(2t+1)}{6}.$

---

For $~i \in \{1,2,\cdots,n\},~$ let $~f(i)~$ denote $~\displaystyle \sum_{j=1}^n |i - j|.~$

Then, you have that

$$\sum_{i=1}^n \sum_{j=1}^n |i - j| = \sum_{i=1}^n f(i).$$

To compute $~f(i),~$ consider the following tableau

  j   =  1    2    3   ... i-1  i  i+1 i+2 ...  n
|i-j| = i-1  i-2  i-3  ...  1   0   1   2  ....n-i

So,

$$f(i) = \sum_{r=1}^{i-1} i-r ~~~~+ ~~~~ \sum_{r=1}^{n-i} i$$

$$= [ ~(i-1)i~] - \frac{(i-1)i}{2} + \frac{(n-i)(n+1-i)}{2}$$

$$= \frac{i^2 - i}{2} + \frac{n^2 + n - 2ni - i + i^2}{2}$$

$$= (i^2) - (n+1)(i) + \frac{n^2 + n}{2}. \tag1 $$

---

So, using the tools T-1 and T-2, and using (1) above, the final computation is

$$\sum_{i=1}^n f(i)$$

$$= \sum_{i=1}^n \left[ ~(i^2) - (n+1)(i) + \frac{n^2 + n}{2} ~\right]$$

$$= \frac{n(n+1)(2n+1)}{6} - \frac{(n+1)^2n}{2} + \frac{n \times (n^2 + n)}{2}$$

$$= n(n+1) ~\left[ ~\frac{2n+1}{6} - \frac{n+1}{2} + \frac{n}{2} ~\right]$$

$$= n(n+1) ~\left[ ~\frac{2n+1}{6} - \frac{1}{2} ~\right]$$

$$= n(n+1) ~\left[ ~\frac{2n-2}{6} ~\right] = n(n+1) ~\left[ ~\frac{n-1}{3} ~\right].$$

Answer 3

There is an instant proof via figurate numbers if you reframe the problem.

Consider an $n x n$ matrix $M$, with rows and columns indexed by $i,j$. If each entry $M_{ij}$ contains $|i-j|$, the sum of the whole matrix is the problem you pose.

The matrix $M$ is easy to envision: $0$ on the main diagonal, $1$ on the 1-diagonals, $2$ on the 2-diagonals, etc. Since the matrix is symmetric, the desired sum will be twice that of the upper triangle.

So consider the upper triangle. To the right of the main diagonal, each row reads ${1,2,3,..}$ until the matrix ends. The top row will run to $n-1$, and each successive row is one entry shorter until the $n^{th}$ row has no entry. The sum of the series ${1,2,3... \ n}$ is called a triangular number, $T_n$. Think of bricks, 1 on top of 2 on top of 3, etc. So the rows of the upper triangle represent $T_{n-1}, T_{n-2},... T_{1}$. Now, lay those triangles flat and imagine you start stacking them to form a triangular pyramid (1 on 3 on 6 on 10, etc.). The sum of the triangular numbers $T_1, T_2,... \ T_n$ is called the tetrahedral number, $Te_n$. The upper triangle of matrix $M$ contains $Te_{n-1}$.

The tetrahedral number for $n$ is $\frac{n(n+1)(n+2)}{6}$.

Thus $Te_{n-1} = \frac{(n-1)(n)(n+1)}{6}$, and the sum you seek is twice that.

You can read more here: https://en.wikipedia.org/wiki/Tetrahedral_number