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

Question

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.

Answer 1

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

Answer 2

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