# Induction Proof: $\sum_{i=1}^{n+1} i \cdot 2^i = n \cdot 2^{n+2}+2$

Prove by Mathematical Induction . . .

$$\sum_{i=1}^{n+1} i \cdot 2^i = n \cdot 2^{n+2}+2$$ for all $n \geq 0$

I tried solving it, but I got stuck near the end . . .

a. Basis Step:

$1\cdot 2^1 = 0\cdot 2^{0+2}+2$

$2 = 2$

b. Inductive Hypothesis

$$\sum_{i=1}^{k+1} i \cdot 2^i = k \cdot 2^{k+2} +2$$ for $k \geq 0$

Prove k+1 is true.

$$\sum_{i=1}^{k+2} i \cdot 2^i = (k+1)\cdot 2^{k+3}+2$$

$\big[RHS\big]$

$k\cdot 2^{k+3}+2^{k+3}+2$

$\big[LHS\big]$

$$\sum_{i=1}^{k+2} {i \cdot 2^{i}}$$

$= \underbrace{\sum_{i=1}^{k+1} i \cdot 2^i} + (k+2)\cdot 2^{k+2}$ (Explicit last step)

$= \underbrace{k\cdot 2^{k+2}+2}+(k+2)\cdot 2^{k+2}$ (Inductive Hypothesis Substitution)

$= k\cdot 2^{k+2}+2+k\cdot 2^{k+2}+2^{k+3}$

$= 2k\cdot 2^{k+2} + 2^{k+3} + 2$

My [LHS] has one too many $2k\cdot 2^{k+2}$ or did it just do it completely wrong?

-
Please use single "$" sign on the title, so it doesn't block much space. – Michael Li Feb 10 '13 at 3:34 I've fixed a couple of spots (in the title and the first paragraph) where you had just 2 but it seems clear from the rest of your question you wanted$2^i$; please correct if those are wrong. – Steven Stadnicki Feb 10 '13 at 3:40 ## 2 Answers You are done. All you need to do is to regroup the terms properly. $$2k \cdot 2^{k+2} + 2^{k+3} + 2 = k \cdot 2^{k+3} + 2^{k+3} + 2 = (k+1) \cdot 2^{k+3} + 2$$ which is what you want. As julien points out, your penultimate step must read $$k \cdot 2^{k+2} + 2 + \color{blue}{k \cdot 2^{k+2}} + 2^{k+3}$$ instead of $$k \cdot 2^{k+2} + 2 + \color{red}{k \cdot 2{k+2}} + 2^{k+3}$$ I assume you made a typo while typesetting this line since you missed the ^ symbol i.e. you have $$\text{k \cdot 2{k+2} instead of k \cdot 2^{k+2}}$$ And also as julien points out, your (Explicit last step) should read $$\color{blue}{\sum_{i=1}^{k+1} i \cdot 2^i} + (k+2) \cdot 2^{k+2}$$ and not $$\color{red}{(k+1) \cdot 2^{k+1}} + (k+2) \cdot 2^{k+2}$$ - Except that there are things that do not make sense along the way of the OP's argument. At least for me. – 1015 Feb 10 '13 at 4:22 thanks a lot i didn't see it for some reason – rbtLong Feb 10 '13 at 5:10 Of course, what you wrote is absolutely correct and that's indeed the last step in this proof. Nevertheless, to get there, the OP replaced$\sum_{i=1}^{k+1}i2^i$by$(k+1)2^{k+1}$. I happen to be wrong sometimes, but here I am 100% sure there is a real problem. And now the OP thinks his/her proof is ok. Could you help? Thanks. – 1015 Feb 10 '13 at 14:54 Thanks, but that was not what I was pointing at. The mistakes I am talking about are in the lines above. – 1015 Feb 10 '13 at 18:27 Attention: you replaced$\sum_{i=1}^{k+1}2^i=2+2\cdot 2^2+3\cdot 2^3+\ldots+(k+1)2^{k+1}$by$(k+1)2^{k+1}$, and this is wrong for$k\geq 2$. The formula holds for$n=0$as you observed. Now assume it holds for some$n\geq 0$, i.e. $$\sum_{i=1}^{n+1}i2^i=n2^{n+2}+2.$$ Then $$\sum_{i=1}^{n+2}i2^i=\sum_{i=1}^{n+1}i2^i+(n+2)2^{n+2}$$ (so, using the induction hypothesis) $$=n2^{n+2}+2+(n+2)2^{n+2}$$ (so, simplifying) $$=2n2^{n+2}+2^{n+3}+2=n2^{n+3}+2^{n+3}+2=(n+1)2^{n+3}+2.$$ So, by induction, the formula holds for all$n\geq 0$. - you said my two last steps are wrong. . . but in your answer, you proved it to be the same using an answer that resemebles my last step exactly. also, marvis proved it correct the same so how can it be wrong? – rbtLong Feb 10 '13 at 5:10 @rbtLong No I did not say that. I said that two steps are wrong. Not the last two. Again, you replaced (twice)$\sum_{i=1}^{k+1}i2^i$by$(k+1)2^{k+1}\$. And this is obviously wrong. Marvis proved an equality which is correct. But he probably did not notice your wrong steps. – 1015 Feb 10 '13 at 14:27
my apologies . . . – rbtLong Feb 11 '13 at 1:46
@rbtLong No problem. I am glad you got it right in the end. – 1015 Feb 11 '13 at 2:29