Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove by induction that $(n+1)+(n+2)\cdots+2n=\frac{1}{2}n(3n+1)$

I was not really sure how to do this, but I assumed that the case holds for $n=k$, therefore $\displaystyle\sum_{r=1}^kk+r=\frac{1}{2}k(3k+1)$.

Want it on this form:$$\frac{1}{2}(2k+1)(6k+3)=\frac{1}{2}12k^2+12k+3$$ Process: $$\displaystyle\sum_{r=1}^k(k+r)+(k+k+1)=\frac{1}{2}(3k^2+k)+(2k+1)$$ $$=\frac{3k^2+5k+2}{2}$$

Im very confused here, and I'm sure there are loads of mistakes here but I just can't spot them. Could anyone be so kind to help?

Thanks,

share|improve this question
add comment

6 Answers 6

up vote 2 down vote accepted

Your induction hypothesis

$$\sum_{r=1}^k(k+r)=\frac12k(3k+1)$$

is fine, but you went astray at the start of the induction step. The $k+1$ case is

$$\sum_{r=1}^{k+1}\big((k+1)+r\big)=\frac12(k+1)\big(3(k+1)+1\big)\;,$$

so you should be starting with

$$\begin{align*} \sum_{r=1}^{k+1}\big((k+1)+r\big)&=\sum_{r=1}^k\big((k+1)+r\big)+\big((k+1)+(k+1)\big)\\ &=\sum_{r=1}^k\big((k+r)+1\big)+2(k+1)\\ &=\sum_{r=1}^k(k+r)+\sum_{r=1}^k1+2(k+1)\\ &=\sum_{r=1}^k(k+r)+k+2(k+1)\\ &=\sum_{r=1}^k(k+r)+3k+2\;. \end{align*}$$

Now you can apply your induction hypothesis and simplify.

share|improve this answer
    
The second step should be $\sum_{r=1}^k ((k+r)+1) + 2(k+1)$ which will lead to final equality being $\sum_{r=1}^k (k+r) + 3k + 2 $ –  user62089 Mar 18 '13 at 19:16
    
@pondy: Thanks for catching it; fixed. –  Brian M. Scott Mar 18 '13 at 19:19
add comment

Hint:its easy to prove by induction :$$1+2+3+...+n=\frac{n(n+1)}{2}$$$$(n+1)+(n+2)\cdots+2n=(n+n+...+n)+(1+2+3+..+n)=n^2+\frac{n(n+1)}{2}$$

share|improve this answer
    
The first line has a typo :-O –  Ben Mar 18 '13 at 19:08
    
@Ben thanks Ben –  Maisam Hedyelloo Mar 18 '13 at 19:10
    
But that's not by induction. You're using a result ($1+2+3+\cdots$) that can be proven by induction, but you're not using induction in your proof. –  Elmar Zander Mar 18 '13 at 19:13
    
@Elmar Zander: hi notice i proved by induction that $1+2+3+...+n=\frac{n(n+1)}{2}$ then by using of it iww prove by induction that $(n+1)+(n+2)\cdots+2n=\frac{1}{2}n(3n+1)$ induction step :$1+1=\frac{1}{2}(3+1)=1$ then i know $(n+1)+(n+2)\cdots+2n=(n+n+...+n)+(1+2+3+..+n)=n^2+\frac{n(n+1)}{2}$ and i will prove $((n+1)+1)+((n+1)+2)\cdots+2(n+1)=\frac{1}{2}(n+1)(3(n+1)+1)$ –  Maisam Hedyelloo Mar 18 '13 at 19:17
    
@MaisamHedyelloo I'm sorry, but you did not prove that. Neither by induction, nor in any other way. You just use that formula. –  Elmar Zander Mar 18 '13 at 19:19
add comment

Hint: it's easy to verify the result for $n=1$.

Now $$((n+1)+1)+((n+1)+2)+\cdots+2(n+1)=(n+2)+(n+3)+\cdots+(2n+2)\\ =\frac{1}{2}n(3n+1)-(n+1)+(2n+1)+(2n+2)$$ and verify that's equal to $\frac{1}{2}(n+1)(3(n+1)+1)$.

share|improve this answer
add comment

Hint:

For the case $n+1$ develop the right part: $1/2(n+1)(3(n+1)+1)$ to come back to the case $n$ plus something and check that whats left is equal to what is in more on the left part for $n+1$ (be careful that there is also one term in less in the sum ...)

share|improve this answer
add comment

Now assume that the identity holds true for $n = k$. This implies

$$ \sum_{r=1}^k (k+r) = \frac 12 k(3k+1)$$

Then for $k+1$ we have,

$$\sum_{r=1}^{k+1} (k+1+r) = \sum_{r=1}^{k} (k+1+r) + 2(k+1) = \sum_{r=1}^{k} (k+r) + \sum_{r=1}^k 1 + 2(k+1) $$ $$= \sum_{r=1}^{k} (k+r) + k + 2(k+1) = \frac 12 k(3k+1) + k + 2(k+1)$$ $$ = \frac 12 (k+1)(3(k+1)+1) $$

share|improve this answer
add comment

Check for $n=1$:

$$(n+1)+\cdots+2n=2=\frac12 1(3+1)=2$$

Ok, that holds. Now see that you can prove the case $n+1$ from the case for $n$

$$((n+1)+1)+\cdots +2(n+1)=(n+1)+\cdots+2n - (n+1)+(2n+1)+(2n+2)$$

Here you can use the fact that the formula olds for $n$:

\begin{align} \ldots &=\frac12 n(3n+1) - (n+1)+(2n+1)+(2n+2)\\ &=\frac12 n(3n+1) + (3n+2)\\ &=\frac12 (3n^2+7n+4)\\ &=\frac12 (n+1)(3(n+1)+1)\\ \end{align}

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.