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

Question

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?

Answer 1

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

Answer 2

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