4
$\begingroup$

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

  • 0
    Paul: Are you familiar with [summation notation](http://en.wikipedia.org/wiki/Summation)?2011-09-18

4 Answers 4

12

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

  • 0
    I like this rearrangement~2011-09-18
8

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.

  • 0
    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)$.2011-09-19
6

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

4

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