1

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.

Jean-Claude Arbaut
  • 22,563
  • 7
  • 50
  • 82
Tina
  • 523
  • 5
  • 14

3 Answers3

1

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}$$

Jean-Claude Arbaut
  • 22,563
  • 7
  • 50
  • 82
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}$$

Hypergeometricx
  • 22,229
  • 2
  • 30
  • 83
  • This looks interesting as it is fast, so I will endeavour to understand it :). Should this step be : $ \sum ^{n}_{i=1}\sum ^{i}_{k=0}k = \sum ^{n}_{i=1}\sum ^{i}_{k=1}$ not be $\sum ^{n}_{i=1}\sum ^{i-1}_{k=1}k$ – Tina Jun 04 '18 at 08:07
  • Yes its an interesting method. You're right, it's $\sum_{i=1}^n\sum_{k=0 (\text{or $1$})} ^{i-1}k$. – Hypergeometricx Jun 04 '18 at 15:00
  • Ok, that makes sense, I just don't understand this step $=\sum_{i=1}^n \binom i2\\ =\binom {n+1}3\\$ – Tina Jun 04 '18 at 17:53
  • 1
    [This](https://en.wikipedia.org/wiki/Hockey-stick_identity) might help. – Hypergeometricx Jun 05 '18 at 14:12
1

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}

Elias Costa
  • 14,200
  • 5
  • 44
  • 82