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

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,

-

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

-
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

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

-

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

-
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

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

-

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

-

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}

-