1
$\begingroup$

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

enter image description here

But I can't figure out why.

$\endgroup$
  • 1
    $\begingroup$ Compute the inner sum first. $\endgroup$ – Claude Leibovici Nov 11 '14 at 7:24
  • $\begingroup$ It depeneds on i, What I got so far is that it equals to: $0*n + 1(n-1) + 2(n-2)+...+n-1(1)+n*0$ which is kind of a sum that the first half equals to the other half. $\endgroup$ – wannabe programmer Nov 11 '14 at 7:30
1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.