# Prove $\sum_{k=0}^n k4^k = \frac 49((3n-1)4^n + 1)$ by induction

Prove that for every position integer $n$ that

$$\sum_{k=0}^n k4^k = \frac 49((3n-1)4^n + 1)$$

Proof: Let $P(n)$ denote the above statement.

Base case: $n=1$ : Note that $$\sum_{k=1}^1 k4^k = \frac 49((3(1)-1)4^{(1)} + 1)$$

$\frac 49((3(1)-1)4^{(1)} + 1) = \frac49((2)4+1) = \frac49(8+1) = \frac 49(9) = 4$

$k4^k = (1)4^{(1)} = 4$

So P(1) holds.

Inductive Step: Let $s\ge1$. Assume P(s), so

$$\sum_{k=1}^s k4^k = \frac 49((3s-1)4^s + 1)$$

Note

$$\sum_{k=1}^{s+1} k4^k = \sum_{k=1}^{s} k4^k + (s+1)4^{s+1}$$

and by inductive hypothesis:

**

$$\frac 49((3s-1)4^s + 1) + (s+1)4^{s+1}$$ **

I'm afraid I'm stuck after this point. I know my endpoint needs to be:

$$\sum_{k=1}^{s+1} k4^k = \frac 49((3(s+1)-1)4^{s+1} + 1)$$

but I don't know how to get from the asterisks to the above. Any help would be greatly appreciated.

So starting from where you ended we just have to manipulate properly:

$$\frac{4}{9}((3s - 1)4^s + 1) + (s + 1)4^{s + 1}$$

$$= \frac{4}{3}s4^s - \frac{4}{9}4^s + \frac{4}{9} + s4^{s + 1} + 4^{s + 1}$$

$$=\Big( \frac{s}{3} - \frac{1}{9} + s + 1 \Big)4^{s + 1} + \frac{4}{9}$$

$$=\frac{4}{9}\Big( (3s + 2)4^{s + 1} + 1 \Big)$$

$$=\frac{4}{9}\Big( (3(s + 1) - 1)4^{s + 1} + 1 \Big)$$

• Got called in to work and just came back, thank you so much, gives me hope that I can eventually do these problems on my own – bankey Nov 19 '15 at 3:37

All you need to do is expand the expression you got after using the inductive hypothesis (in general, if you don't know where to go, at least do something you know you can do!). You get:

$$\begin{split} \frac{4}{9}((3s-1)4^s+1)+(s+1)4^{s+1}&= \frac{1}{9}(3s-1)4^{s+1}+\frac{4}{9}+s\cdot 4^{s+1}+4^{s+1} \\ &=\frac{1}{3}s\cdot 4^{s+1}-\frac{1}{9}4^{s+1}+\frac{4}{9}+s4^{s+1}+4^{s+1} \\ &=4^{s+1}\left[\frac{s}{3}-\frac{1}{9}+s+1 \right]+\frac{4}{9} \\ &= 4^{s+1} \left[ \frac{3s-1+9s+9}{9}\right]+\frac{4}{9} \\ &= 4^{s+1} \left[\frac{12s+8}{9} \right] \\ &= \frac{4}{9}[(3s+2)4^{s+1}+1] \\ &=\frac{4}{9}[(3(s+1)-1)4^{s+1}+1] \end{split}$$

• Thank you so much :) helps a lot. Still in learning process of induction and gives me a lot of hope that I can succeed in future attempts :) – bankey Nov 19 '15 at 3:38