How to show the double sum identity $\sum ^{n}_{i=1}\sum ^{i}_{j=1}i-j$ = $\dfrac {1}{6}n\left( n-1\right) \left( n+1\right) $

Question

I am not sure how to go about showing this: $\sum ^{n}_{i=1}\sum ^{i}_{j=1}i-j$ = $\dfrac {1}{6}n\left( n-1\right) \left( n+1\right) $

It is a bit like the formula for $\sum ^{n}_{i=1}i^{2}$

and this $\sum_{i=1}^n \sum_{j=1}^i \frac{i-j}{nm} + \sum_{i=1}^{n} \sum_{j=i}^m \frac{j-i}{nm} = \frac{2 n^2 - 3 n m + 3 m^2 - 2}{6m}$

As I really do not know how to proceed.

Answer 1

$$\begin{align} \sum_{i=1}^n\sum_{j=1}^i(i-j) &=\sum_{i=1}^n\sum_{k=0}^{i-1} k &&\scriptsize (k=i-j)\\ &=\sum_{i=1}^n \binom i2\\ &=\binom {n+1}3\\ &=\frac 16 (n-1)n(n+1) \qquad\blacksquare \end{align}$$

Answer 2

First

$$\sum_{j=1}^i (i-j)=\sum_{j=1}^i i-\sum_{j=1}^i j=i^2-\frac{i(i+1)}{2}=\frac{i^2}{2}-\frac{i}{2}$$

Thus

$$\sum_{i=1}^n\left(\sum_{j=1}^i (i-j)\right)=\frac12\sum_{i=1}^ni^2-\frac12\sum_{i=1}^ni\\=\frac{n(n+1)(2n+1)}{12}-\frac{n(n+1)}{4}=\frac{2n^3+3n^2+n-3n^2-3n}{12}\\=\frac{2n^3-2n}{12}=\frac{n(n-1)(n+1)}{6}$$

Here I used the fact, proved here, that

$$\sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}{6}$$

Answer 3

I would suggest an inductive proof to that identity. Assume the induction hipotesis $$ \sum^{n}_{i=1}\sum^{i}_{j=1}i-j= \dfrac{1}{6}n\left( n-1\right) \left( n+1\right). $$ It's easy to verify identity for $n=1$, $n=2$ and $n=3$. Consider the scheme. $$ \begin{array}{rl} \sum^{n}_{i=1}\sum^{i}_{j=1}i-j=&0 \\ +&0+1 \\ +&0+1+2 \\ +&0+1+2+3 \\ +&0+1+2+3+4 \\ &\vdots \;\;\;\,\vdots \;\;\;\,\vdots \;\;\;\, \vdots \;\;\;\, \vdots \;\;\;\, \ddots \\ +&0+1+2+3+4+\cdots +i \\ &\vdots \;\;\;\,\vdots \;\;\;\,\vdots \;\;\;\, \vdots \;\;\;\,\vdots \;\;\;\, \quad \;\;\;\, \vdots \;\;\;\,\ddots \\ +&0+1+2+3+4+\cdots +i+\cdots+(n-1) \end{array} $$ Note by scheme that \begin{align} \sum^{n+1}_{i=1}\sum^{i}_{j=1}i-j &= \left[\sum^{n}_{i=1}\sum^{i}_{j=1}i-j\right]+\big[ 1+2+3+\ldots +n\big] \end{align} By induction hipotesis we have \begin{align} \sum^{n+1}_{i=1}\sum^{i}_{j=1}i-j &= \left[\dfrac{1}{6}\left( n-1\right)n\left( n+1\right)\right]+\big[ 1+2+3+\ldots +n\big] \end{align} And since we know that $\dfrac{1}{2}n(n+1)$ is the result of the sum $1+2+3+\ldots +n$ we have \begin{align} \sum^{n+1}_{i=1}\sum^{i}_{j=1}i-j &= \dfrac{1}{6}( n-1)n(n+1)+ \dfrac{1}{2}n(n+1) \\ &= \dfrac{1}{6}(n-1)n(n+1)+ \dfrac{3}{6}n(n+1) \\ &= \Big[(n-1)+ 3\Big]\dfrac{1}{6}n( n+1) \\ &= \dfrac{1}{6}n\cdot (n+1)(n+2) \\ &= \dfrac{1}{6}[\color{red}{(n+1)}-1]\cdot [\color{red}{(n+1)}][\color{red}{(n+1)}+1] \end{align}