I have to prove the following proposition:
$$\sum_{i = 1}^{n} i\cdot 2^i = (n – 1) \cdot 2^{n + 1} + 2$$
I have the following proof thus far:
Proof by Induction
Basis Step $(n = 1)$
LHS: $\sum_{i = 1}^{n} i2^i = 1 \cdot 2^1 = 2$
RHS: $2^2(0) + 2 = 2$
LHS = RHS
Inductive Hypothesis
Assume that the proposition is true for $i = 1, 2, 3, \ldots, k$
Inductive Step $(n = k + 1)$
LHS: $\sum_{i = 1}^{k} i2^i + (k + 1) \cdot 2^{k + 1} = 1 \cdot 2^1 + 2 \cdot 2^2 + \ldots + k \cdot 2^k + (k + 1) \cdot 2^{k + 1}$
RHS: $(k – 1) \cdot 2^{k + 1} + 2 + (k + 1) \cdot 2^{k + 1}\\ = (k – 1) \cdot 2^{k + 1} + (k + 1) \cdot 2^{k + 1} + 2\\ = ((k – 1) + (k + 1)) \cdot 2^{k + 1} + 2\\ = (2k) \cdot 2^{k + 1} + 2$
LHS = RHS
QED
Am I correct? If not, am I headed in the right direction? I understand the basics of induction, but am continuing to apply it. Thank you!
Best Answer
Your base case is correct, but you need more information in the inductive hypothesis.
Base Case: $(n = 1)$ $$\sum_{i=1}^{1}i2^i = 1\cdot 2^1 = 2 = (1-1) \cdot 2^{1+1} + 2 $$ Inductive Hypothesis: Assume that $$\sum_{i=1}^{k} i2^i = (k-1) \cdot 2^{k+1} + 2 \hspace{1in} \text{IH}$$ for some integer $k >1$. You must show that $$\sum_{i=1}^{k+1} i2^i = k2^{k+2} + 2$$ Inductive Step: $$\sum_{i=1}^{k+1} i2^i = \sum_{i=1}^{k} i2^i+ \sum_{i=k+1}^{k+1} i2^i = (k-1) \cdot 2^{k+1} + 2 + (k+1)\cdot 2^{k+1} \hspace{.5in} \text{By IH}$$ $$= (k-1)\cdot 2^{k+1} + 2$$ $$= 2^{k+1} [ (k-1) + (k+1)] + 2$$ $$= 2^{k+1}\cdot 2k + 2$$ $$= k2^{k+1}\cdot 2^1 + 2$$ $$= k2^{k+2} + 2$$ Thus, $\sum_{i=1}^{n} i2^i = (n-1) \cdot 2^{n+1} + 2 \ \text{for any } n\geq 1$
QED