Why is this nested sum formula true

Question

I've been trying to get this sum: $\sum_{i}^{n} \sum_{j=0}^{n-i}j$ into a closed formula but couldn't really understand how to "unpack" that nested sum.

It occured to me that the answer is: $$\sum_{i=1}^n \left(\sum_{j=0}^{n-i} j\right) = \frac16 n (n^2-1)$$

But I can't figure out why.

Answer 1

From sum of first n natural numbers, we get $$\sum_{i = 1}^{n}\sum_{j = 0}^{n - i}j = \sum_{i = 1}^{n}\frac{(n - i)(n - i + 1)}{2}$$ $$=\frac{1}{2}\sum_{i = 1}^{n}n^2 - (2n + 1)i +i^2+n$$ $$=\frac{n^3}{2} + \frac{n^2}{2} - (2n + 1)\frac{1}{2}\sum_{i = 1}^{n}i + \frac{1}{2}\sum_{i = 1}^{n}i^2$$ Using sum of first n natural numbers and sum of first n squares, we get $$=\frac{n^3}{2} + \frac{n^2}{2} - \frac{n(n+1)(2n + 1)}{4} + \frac{n(n+1)(2n+1)}{12}$$ $$=\frac{n^3}{2} + \frac{n^2}{2} - \frac{n(n+1)(2n + 1)}{6}$$ $$=\frac{n^3}{2} + \frac{n^2}{2} - \frac{2n^3 + 3n^2 + n}{6}$$ $$= \frac{3n^3 + 3n^2 - 2n^3 - 3n^2 - n}{6}$$ $$= \frac{n^3 - n}{6}$$ $$= \frac{n(n^2 - 1)}{6}$$

Answer 2

You know that:

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

Then:

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

The remaining part you can find easily as difference between the sum above and its value on i=0:

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

Answer 3

Use the identity

$$\sum_{r=a}^{n}{r\choose a}={n+1\choose a+1}$$

Hence $$\begin{align} \sum_{i=1}^n\sum_{j=0}^{n-i}j&=\sum_{i=1}^n\sum_{j=0}^{n-i}\binom j{\color{red}{1}} =\sum_{i=1}^n\binom{n-i+1}2\\ &=\sum_{r=1}^n\binom r{\color{red}2}\qquad \text{putting $r=n-i+1$}\\ &=\binom{n+1}{\color{red}3} =\frac{(n+1)n(n-1)}{1\cdot 2\cdot 3}\\ &=\frac16n(n^2-1)\qquad \blacksquare \end{align}$$

Answer 4

A little figure immediately shows that the sum ($=:Q$) can be written as $$Q=\sum_{(i,j)\in T} j\ ,$$ where $T$ is following triangle of lattice points: $$T:=\bigl\{(i,j)\in{\mathbb Z}\>\bigm|\>i\geq1, \ j\geq 0,\ i+j\leq n\bigr\}\ .$$ Interchanging the order of summation then gives $$Q=\sum_{j=0}^{n-1} j\left(\sum_{i=1}^{n-j} 1\right)=n \sum_{j=0}^{n-1} j-\sum_{j=0}^{n-1} j^2={(n-1)n^2\over2}-{(n-1)n(2n-1)\over6}={n(n^2-1)\over6}\ .$$