Solving Recurrence Relations using Iteration

Question

$$a_0 = 2; \qquad a_k=4a_{k-1}+5 ~ \forall\ k\ge 1$$

I have already tried solving for $a_1$ through $a_5$.

Answer 1

$$\begin{align*} a_k - a_{k-1} & = 4a_{k-1}+5 -(4a_{k-2}+5) \\ &= 4(a_{k-1} - a_{k-2}) \\ &= 4^2(a_{k-2}-a_{k-3}) \\ & =4^{k-1}(a_1-a_0) \\ & =11\cdot 4^{k-1} \\ \Rightarrow a_k & = (a_k-a_{k-1})+(a_{k-1} - a_{k-2})+\cdots +(a_1-a_0)+a_0 \\ & = 11\cdot 4^{k-1} +11\cdot 4^{k-2} +\cdots + 11\cdot 4 + 11 + 2 \\ & = \ldots \end{align*}$$

Answer 2

Another way to handle problems of this general type is to use the $Z$-transform, where the $Z$-transform $A(z)$ of the sequence $a_n$ is given by

$$A(z)=\sum_{n=0}^{\infty}a_nz^{-n}$$

We know that the $Z$-transform of $a_{n+1}$ is given by

$$\sum_{n=0}^{\infty}a_{n+1}z^{-n}=z^{-1}A(z)-z^{-1}a_0$$

So, let's apply the $Z$-transform to the series $a_{n+1}-4a_n=0$ with $a_0=2$.

Taking the $Z$-transform yields

$$zA(z)-za_0-4A(z)=0$$

whereupon solving for $A$ reveals

$$A(z) = a_0\frac{z}{z-4}$$

But we know that the $Z$-transform $R(z)$ of $r^n$ is $\frac{z}{z-r}$ (geometric series in $r/z$).

So, we find that $a_n$ is

$$a_n=2\, (4^n)$$

Answer 3

Let $a_k = b_k + c$. We then obtain that $$b_{k} + c= 4b_{k-1} + 4c + 5 \implies b_k = 4b_{k-1} + 3c+5$$ Setting $c=-5/3$, we see that $b_k = 4b_{k-1} \implies b_k = 4^kb_0$. Further, we have $a_0 = b_0 - 5/3 = 2 \implies b_0 = 11/3$. Hence, we obtain $$b_k = \dfrac{11}3 \cdot 4^k \implies a_k = \dfrac{11}3 \cdot 4^k - \dfrac53$$