Recurrence relation solution $a_{k+1} = 4a_k + 16^k.$

Question

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.

Answer 1

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.

Answer 2

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.