<s>[INST] 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.
 [/INST] 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)$$
</s>