6
$\begingroup$

How can I calculate $1+(1+2)+(1+2+3)+\cdots+(1+2+3+\cdots+n)$? I know that $1+2+\cdots+n=\dfrac{n+1}{2}\dot\ n$. But what should I do next?

$\endgroup$
11
$\begingroup$

Hint: use also that $$ 1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}6 $$

$$ 1 + (1+2) + \dots + (1 +2+\dots +n) = \frac{1(1+1)}2 + \frac{2(2+1)}2 + \dots + \frac{n(n+1)}2 \\=\frac 12 \left[ (1^2 + 1) + (2^2 + 2 ) + \dots + (n^2 + n) \right] \\=\frac 12 \left[ (1^2 + 2^2 + \dots + n^2) + (1 + 2 + \dots + n) \right] $$

$\endgroup$
12
$\begingroup$

Pascal Triangle

Sorry for the horrible resolution. In any case: That's Pascal's triangle. The blue is the triangular numbers. The red is the sum of the blue (can you see why?)

Now you can use the formula for the elements of Pascal's triangle: The $n$th row and $r$th column is $\dbinom nr$. (You start counting the rows and columns from 0. The rows can be counted from the left or the right, doesn't matter.)

The answer is $\dbinom{n+2}3=\dfrac{n(n+1)(n+2)}{3!}$.

$\endgroup$
  • $\begingroup$ Can you see why the blue are the triangular numbers, by the way? $\endgroup$ – Akiva Weinberger Oct 19 '14 at 15:21
  • $\begingroup$ +1 for not just offering the combinatorial answer (which is much cleaner than going through any sum-of-squares formula) but doing a great job of explaining why it's true. This is IMHO the best answer by far here. $\endgroup$ – Steven Stadnicki Oct 19 '14 at 16:24
  • $\begingroup$ brilliant!${{{}}}$ $\endgroup$ – mookid Oct 19 '14 at 16:25
3
$\begingroup$

$$\begin{align} &1+(1+2)+(1+2+3)+\cdots+(1+2+3+\cdots+n)\\ &=n\cdot 1+(n-2)\cdot 2+(n-3)\cdot 3+\cdots +1\cdot n\\ &=\sum_{r=1}^n(n+1-r)r\\ &=\sum_{r=1}^n {n+1-r\choose 1}{r\choose 1}\\ &={n+2\choose 1+2}\\ &={n+2\choose 3}\\ &=\frac16 n(n+1)(n+2) \end{align}$$

$\endgroup$
  • $\begingroup$ This seems to be wrong as the last expression is the sum of the first $\;n\;$ squared natural numbers, which is not what we have. $\endgroup$ – Timbuc Oct 19 '14 at 16:16
  • 1
    $\begingroup$ Not really... the sum of the first $n$ squared natural numbers is $\frac16 n(n+1)(2n+1)$ $\endgroup$ – hypergeometric Oct 19 '14 at 16:18
  • $\begingroup$ Oh, I see now the second parentheses more carefully. Thanks. +1 $\endgroup$ – Timbuc Oct 19 '14 at 16:24
3
$\begingroup$

$$\sum_{k=1}^n(1+\ldots+k)=\sum_{k=1}^n\frac{k(k+1)}2=\frac12\left(\sum_{k=1}^nk^2+\sum_{k=1}^nk\right)$$

and now

$$\sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}6$$

$\endgroup$
1
$\begingroup$

HINT :

It is the summation of $\sum \frac {n(n+1)}2$ from 1 to n

which is equal to $\sum (\frac {n^2}2 + \frac n2)$ from 1 to n

$\endgroup$
1
$\begingroup$

I thought about this problem differently than others so far. The problem is asking you to essentially sum up a bunch of sums. So by observation, it appears that $1$ appears $n$ times, $2$ appears $n-1$ times, $3, n-2$ times and so on, with only $1$ $n$ term. So instead, let's add up a sum from $1$ to $n$ which does this. It should be of the form $\sum_{i=1}^{n} n(n+1)=\sum_{i=1}^{n}n^2+n.$ Since sums are linear, decompose this into two sums, and apply the formulas you know for the sum of the squares and the sum of the integers.

$\endgroup$
1
$\begingroup$

Sums we know:
$\sum^n_{i=1} i = 1+2+\cdots+n=\frac{n^2+n}{2}$
$\sum^n_{i=1} i^2 = 1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}6$

Your sum is $$(1+2+3+ \cdots + n) + (1 + 2 + \cdots + (n-1)) + (1 + 2 + \cdots + (n-2)) + \cdots + (1)$$ $$= \sum^n_{k=1} \sum^k_{i=1} i$$ $$= \sum^n_{k=1} \frac{k^2+k}{2} = \frac 12 (\sum^n_{k=1} k^2 + \sum^n_{k=1} k)$$

NOTE: You can reorder the terms if the are a finite number of them. So if you're going to be taking a limit as $n \to \infty$ don't do it this way.

$\endgroup$
1
$\begingroup$

The n-th partial sum of the triangular numbers as listed in http://oeis.org/A000292 .

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