# 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?

-