2
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

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

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

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

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.