# Is there a formula for a simple sum of sums?

Given $f(n) = 1 + (1 + 2) + (1 + 2 + 3)+ \cdots + (1 + 2 + 3 +\cdots + n)$, I am wondering if there is a straightforward formula to compute f(n) and how it may be derived.

The only reduction I thought about so far would be:

n*1 + (n - 1)*2 + (n - 3)*3 ... which seems symmetrical; for example, an odd and even n

 5 4 3 2 1        4 3 2 1
*                *
1 2 3 4 5        1 2 3 4


but I'm not sure if and how it may help derive a formula.

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

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

Using two well known identitites,

$$f(n)=\frac12\left(\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\right)$$

Simplifying:

$$f(n)=\frac{n(n+1)}{4}\left(\frac{2n+1}{3}+1\right)$$

$$f(n)=\frac{n(n+1)}{4}\left(\frac{2n+4}{3}\right)$$

$$f(n)=\frac{n(n+1)}{2}\left(\frac{n+2}{3}\right)$$

$$f(n)=\frac{n(n+1)(n+2)}{6}$$

• Thanks for helping me think about it in a new way. – גלעד ברקן Mar 15 '14 at 11:53
• nice answer@Sabyasachi – Semsem Mar 15 '14 at 12:02

There is a general formula $$\sum_{k=1}^n\frac {k(k+1)\dots(k+r-1)}{r!}=\frac {n(n+1)\dots(n+r)}{(r+1)!}$$

Which can be proved by induction - base case $n=1$, both sides of the equation are equal to $1$.

Then $$\frac {n\left[(n+1)\dots(n+r)\right]}{(r+1)!}+\frac {\left[(n+1)\dots(n+r)\right]}{r!}=\frac {\left[(n+1)\dots(n+r)\right](n+r+1)}{(r+1)!}$$

Another way of writing this, which invites a combinatorial proof is:

$$\sum_{k=1}^n\binom {k+r-1}r=\binom {n+r}{r+1}$$

The sum of integers is the case $r=1$ and the sum of triangular numbers is the case $r=2$.

• Wow. I didn't know this. Will be very useful. +1. – Guy Mar 15 '14 at 14:15
• @Sabyasachi I mistyped the final formula, if you are checking, and have now corrected it – Mark Bennet Mar 15 '14 at 14:52
• Okay thanks for the correction. – Guy Mar 15 '14 at 15:02