6
$\begingroup$

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.

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

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.

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

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

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.