Recurrence relation solution $a_{k+1} = 4a_k + 16^k.$ How can I find the closed form of $a_{k+1} = 4a_k + 16^k$?
I tried to look for a pattern, but I cannot find one.
$a_1 = 1,$ also.
 A: Here is a hint. There is a general theory here - if you discover it yourself, count yourself truly competent.
(1) Suppose you have a solution $a_k$ and also a solution to the homogeneous equation $b_{k+1}=4b_k$ then what can you say about $c_k=a_k+Bb_k$?
(2) What is the simplest possible test function you can think of for $a_k=f(k)$?
(3) You have not specified an initial value, so any general solution will depend on the initial value (eg $a_1$ or $a_0$). Any general solution you find which doesn't reference an initial value will be wrong.
A: Because this is a first-order recurrence, it will also succumb to the very elementary approach of ‘unwinding’ it:
$$\begin{align*}
a_n&=4a_{n-1}+16^{n-1}\\
&=4\left(4a_{n-2}+16^{n-2}\right)+16^{n-1}\\
&=4^2a_{n-2}+4\cdot16^{n-2}+16^{n-1}\\
&=4^2\left(4a_{n-3}+16^{n-3}\right)+4\cdot16^{n-2}+16^{n-1}\\
&=4^3a_{n-3}+4^2\cdot16^{n-3}+4\cdot16^{n-2}+16^{n-1}\\
&\;\;\vdots\\
&=4^ka_{n-k}+\sum_{i=0}^{k-1}4^i\cdot16^{n-i-1}\\
&\;\;\vdots\\
&=4^{n-1}a_1+\sum_{i=0}^{n-2}4^i\cdot16^{n-i-1}\\
&=4^{n-1}+16^{n-1}\sum_{i=0}^{n-2}\left(\frac14\right)^i\\
&=4^{n-1}+16^{n-1}\cdot\frac{1-(1/4)^{n-1}}{3/4}\\
&=4^{n-1}+\frac43\cdot\left(16^{n-1}-4^{n-1}\right)\\
&=\frac{4\cdot16^{n-1}-4^{n-1}}3\\
&=\frac{4^{2n-1}-4^{n-1}}3\\
&=\frac{4^{n-1}\left(4^n-1\right)}3
\end{align*}$$
Of course that step in the middle with $a_{n-k}$ isn’t really rigorous. It’s recognizing the pattern that has developed and pretty clearly will continue, but you should verify that the final closed form actually does satisfy the recurrence; this can be done with a proof by induction that is generally (and in this case) pretty straightforward.
