How to deduce sum's result?

Question

I was solving some tricky-task with algorithms and I obtained following reccurence:

$$a_{k+1} = 4a_{k} + 16^{k}, a_{1} = 1$$

It's obvious that with given start condition: $$a_{k+1} = 4a_{k} + 16^{k} = 16^{k} + 4 \cdot 16^{k-1} + 4^{2} \cdot 16^{k-2} + 4^{3} \cdot 16^{k-3} + ... + 4^{k} \cdot 16^{0} = \sum_{k=0}^{n} { 4^{k} \cdot 16^{n-k} } =\sum_{k=0}^{n} { 4^{2n - k} } $$

This sum seems very familiar but I can't solve it - WAlpha shows as a result $\frac{1}{3}4^{n}(4^{n+1} -1)$. I assume it's easy to prove that by induction, but I'm interested in straight-forward (maybe? combinatorial) proof.

I'll be thankful for any help. Thanks in advance!

Answer 1

HINT: $$\sum_{k=0}^{n} { 4^{2n - k} }=4^{2n}\sum_{k=0}^{n}4^{-k}$$

also, $\sum\limits_{k=0}^{n}4^{-k}$ is the sum for a geometric progression.

Can you take it from here?

Answer 2

Since $n$ is independent of $k$,

$$\sum_{k=0}^{n}4^{2n - k} = 4^{2n}\sum_{k=0}^{n}4^{-k} = 4^{2n}\sum_{k=0}^{n}(\frac14)^k = 4^{2n}\cdot\frac{1 - (\frac14)^{n+1}}{1 - \frac14} = etc.$$