# How can the following be calculated?

How can the following series be calculated?

$$S=1+(1+2)+(1+2+3)+(1+2+3+4)+\cdots+(1+2+3+4+\cdots+2011)$$

-
That's completely false; check $n=1$ and you get $1+1=1$. You might want to rework your question before someone can answer it. –  anon Sep 18 '11 at 8:15
possible duplicate of Sum of n consecutive numbers –  Raskolnikov Sep 18 '11 at 8:15
@Raskolnikov: It's not evident yet whether OP wanted the sum of the first $n$ consecutive numbers (RHS) or sum of the first $n$ triangular numbers (LHS), so I think the close vote is too preemptive. EDIT: Appears it is the latter, hence this is not a duplicate of the cited question. –  anon Sep 18 '11 at 8:20
OK, just a badly framed question then. –  Raskolnikov Sep 18 '11 at 8:22
Paul: Are you familiar with summation notation? –  anon Sep 18 '11 at 8:23

Note that $1$ occurs $2011$ times; $2$ occurs $2010$ times; $3$ occurs $2009$ times, and so on, until $2011$ occurs only once. Hence we can rewrite the sum as $$(2012-1)(1)+(2012-2)(2)+(2012-3)(3)+\cdots+(2012-2011)(2011).$$ Split and regroup terms: $$2012(1+2+3+\cdots+2011)-(1^2+2^2+3^2+\cdots+2011^2).$$ Now using the two formulas for triangular numbers and square pyramidal numbers, compute $$2012\frac{2011(2011+1)}{2}-\frac{2011(2011+1)(2\cdot2011+1)}{6}=1357477286.$$

This also evaluates the general sum: $$1+(1+2)+\cdots+(1+2+\cdots+n)$$ $$=(n+1-1)(1)+(n+1-2)(2)+\cdots+(n+1-n)(n)$$ $$=(n+1)(1+2+\cdots+n)-(1^2+2^2+\cdots+n^2)$$ $$=(n+1)\frac{n(n+1)}{2}-\frac{n(n+1)(2n+1)}{6}=n(n+1)\left[\frac{n+1}{2}-\frac{2n+1}{6}\right]$$ $$=\frac{n(n+1)(n+2)}{6}.$$ One could also use the triangle number formula on each term for a more direct route: $$\frac{1(1+1)}{2}+\frac{2(2+1)}{2}+\frac{3(3+1)}{2}+\cdots+\frac{n(n+1)}{2}$$ $$=\frac{1}{2}\left[(1+2^2+\cdots+n^2)+(1+2+\cdots+n)\right]$$ $$=\frac{1}{2}\left[\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\right]=\frac{n(n+1)}{4}\left[\frac{2n+1}{3}-1\right]$$ $$=\frac{n(n+1)(n+2)}{6}.$$

-
I like this rearrangement~ –  puresky Sep 18 '11 at 9:04

Let $S$ be our sum. Then $$S=\binom{2}{2}+\binom{3}{2}+\binom{4}{2} + \cdots + \binom{2012}{2}=\binom{2013}{3}=\frac{2013\cdot 2012\cdot 2011}{3 \cdot 2 \cdot 1}.$$

Justification: We count, in two different ways, the number of ways to choose $3$ numbers from the set $$\{1,2,3,4,\dots, n,n+1\}.$$ (For our particular problem we use $n=2012$.)

First Count: It is clear that there are $\binom{n+1}{3}$ ways to choose $3$ numbers from $n+1$ numbers.

Second Count: The smallest chosen number could be $1$. Then there are $\binom{n}{2}$ ways to choose the remaining $2$ numbers.

Or the smallest chosen number could be $2$, leaving $\binom{n-1}{2}$ choices for the remaining $2$ numbers. Or the smallest chosen number could be $3$, leaving $\binom{n-2}{2}$ choices for the remaining $2$ numbers. And so on, up to smallest chosen number being $n-1$, in which case there are $\binom{2}{2}$ ways to choose the remaining $2$ numbers. Thus the total count is $$\binom{n}{2}+\binom{n-1}{2}+\binom{n-2}{2}+\cdots +\binom{3}{2}+\binom{2}{2}.$$

Comparing the two counts, we find that $$\binom{2}{2}+\binom{3}{2}+\binom{4}{2}+\cdots +\binom{n-1}{2}+\binom{n}{2}=\binom{n+1}{3}.$$

Comment: Similarly, it is easy to see that in general $\sum_{k=r}^n \binom{k}{r}=\binom{n+1}{r+1}.$ These natural binomial coefficient identities give a combinatorial approach to finding general formulas for the sums of consecutive squares, consecutive cubes, and so on.

-
Mark. Count-twice method. But it's a proof rather than a calculation. –  puresky Sep 19 '11 at 3:25
It is a calculation together with a proof that the calculation is correct. We end up with the number $(2013\cdot 2012\cdot 2011)/(3\cdot 2 \cdot 1)$. –  André Nicolas Sep 19 '11 at 4:30

Hints: useful formulas are $$\begin{eqnarray*} \sum_{k=1}^N 1 = N \\ \sum_{k=1}^N k = \frac{N(N+1)}{2}\\ \sum_{k=1}^N k^2 = \frac{N(N+1)(2N+1)}{6}\end{eqnarray*}$$

-

If you look at the third differences then you will get a constant, so you know there is a third degree polynomial formula. In fact, since the constant is 1, you also know the coefficient of $n^3$ is $\frac{1}{3!}$.

So just fit the early terms $S_0=0, S_1=1, S_2=4, S_4=10$ to a third degree polynomial and find the result $$S_n = \frac{n^3}{6} +\frac{n^2}{2} +\frac{n}{3}.$$

Then let $n=2011$.

-