# Sum of the first $n$ triangular numbers - induction

Question:

Prove by mathematical induction that $$(1)+(1+2)+(1+2+3)+\cdots+(1+2+3+\cdots+n)=\frac{1}{6}n(n+1)(n+2)$$ is true for all positive integers n.

Attempt:

I did the the induction steps and I got up to here: $$RTP:\frac{1}{6}n(n+1)(n+2)+(1+2+3+\cdots+n+(n+1))=\frac{1}{6}(n+1)(n+2)(n+3)$$ Where do I go from here?

Thank you very much.

• That's it. The expression on the right-hand side is exactly what you want. – Stefan Hansen Apr 29 '13 at 15:17
• But I have to prove that they are equal. – please delete me Apr 29 '13 at 15:18
• Use the formula $1+2+\cdots+n+(n+1)={(n+1)(n+2)\over2}$. Then simplify. – David Mitra Apr 29 '13 at 15:19
• How do I derive this formula? – please delete me Apr 29 '13 at 15:19
• @AlexanderJones Gauss did it when he is in primary school. – Ma Ming Apr 29 '13 at 15:21

## 4 Answers

What you’ve really done up to this point is use your induction hypothesis to say that

$$(1)+(1+2)+\ldots+(1+2+\ldots+n)+\big(1+2+\ldots+n+(n+1)\big)$$

is equal to

$$\frac16n(n+1)(n+2)+\big(1+2+\ldots+n+(n+1)\big)\;.$$

To finish the induction step you must show that this quantity is equal to

$$\frac16(n+1)(n+2)(n+3)\;,$$

i.e., that

$$\frac16n(n+1)(n+2)+\big(1+2+\ldots+n+(n+1)\big)=\frac16(n+1)(n+2)(n+3)\;.\tag{1}$$

In order to do this, you need a nice closed form for the term

$$1+2+\ldots+n+(n+1)\;.$$

I’m sure that by this point you’ve learned a closed form for the sum of the first $m$ consecutive integers; substitute that (with $m=n+1$) for $1+2+\ldots+n+(n+1)$ on the lefthand side of $(1)$, and do some algebra to show that the quantity on the lefthand side then really does simplify to the quantity on the righthand side.

• I should be very much interested in an explanation of the downvote with which all four answers seem to have been ‘graced’. – Brian M. Scott May 10 '13 at 15:05

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

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

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

You can use two nested inductions.

In order to show the equality $\forall n, 1 + (1+2) + (1+2+3) + \ldots (1+2+\ldots+n) = \frac 1 6 n (n+1) (n+2)$, you check that it is true for $n=1$, and then you are left to show the equality $\forall n, \frac 1 6 n (n+1) (n+2) + (1+2+ \ldots+n+(n+1)) = \frac 1 6 (n+1) (n+2) (n+3)$, which can be simplified to $\forall n, (1+2+ \ldots +n+(n+1)) = \frac 1 6 (n+1) (n+2) [(n+3)-n] = \frac 1 2 (n+1) (n+2)$.

Now, you use induction again to prove this. You check that it is true for $n=1$, and are left to show the equality $\forall n, \frac 1 2 (n+1)(n+2) + (n+2) = \frac 1 2 (n+2)(n+3)$. Which should be straightforward to prove.

Alternately you can use a single strong induction : check that it is true for $n=0,1$, and for $n\ge 1$, assume the equality is true for $n-1$ and $n$, and show that it is true for $n+1$, by using $1 + (1+2) + (1+2+3) + \dots + (1+2+\ldots n+1) = 2*(1 + (1+2) + \ldots (1+2+\ldots + n)) - (1+(1+2) + \ldots + (1+2+\ldots +(n-1)) + (n+1)$. Replace everyone with the corresponding $\frac 1 6 k(k+1)(k+2)$, and then it should be straightforward.

The general equation for your expression is $$S= \sum_{k=1}^{n}k(n-k+1)=n \sum_{k=1}^{n}k-\sum_{k=1}^{n}k^2 +\sum_{k=1}^{n}k$$

what you need to know here are $\sum_{k=1}^{n}k=\frac{n(n+1)}{2}$ and $\sum_{k=1}^{n}k^2 = \frac{n(n+1)(2n+1)}{6}$.

You don't need induction to prove these, you may use the perturbation method from $\mathit{Concrete \ Mathematics}$, Chapter 2. I'll do the first sum, the second is similar.

$$S_n +(n+1^2)=\sum_{k=1}^{n}k^2 + (n+1)^2 = 1 + \sum_{k=1}^{n}(k+1)^2 = 1+ S_n +2 \sum_{k=1}^{n}k+n$$ Hence the $S_n$ cancel out, and you get the closed-form expression for $\sum_{k=1}^{n}k$

Once you get these, the rest is very easy:

$$S= \frac{n^2(n+1)}{2}+\frac{n(n+1)}{2}-\frac{n(n+1)(2n+1)}{6}=\frac{n(n+1)(n+2)}{6}$$

• why the downvote? what's wrong with it? – Alex May 10 '13 at 12:07