Finding the closed form for a recurrence relation I'm having trouble finding a closed form for a geometric recurrence relation where the term being recursively multiplied is of the form (x+a) instead of just (x). 
Here's the recursive sequence:
$a_{n} = 4a_{n-1} + 5$ for $n \geq 1$ with the initial condition $a_{0} = 2$.
I know that in general the way to solve these problems is to start by writing out all of the arithmetic for the first few values of $a_{n}$, starting with the initial condition. Here's what I have:
$a_{0} = 2$
$a_{1} = 4 (2) + 5 \equiv ((2)(2)(2) + 5)$
$a_{2} = 4(4(2)+5)+5 \equiv (2)(2)((2)(2)(2)+5)+5$
$a_{3} = 4(4(4(2)+5)+5)+5 \equiv (2)(2)((2)(2)((2)(2)(2)+5)+5)+5$
$\ldots$ etc.
So at this point it's pretty clear to me that
$a_{n} = 2^{2n + 1} + something$
My problem is figuring out how to account for all of those 5's. Especially since the first 5 is being multiplied by $2^{3}$ and all of the other 5's are being multiplied by $2^{2}$. 
I guessed something like this:
$a_{n} = 2^{2n+1} + 5(4^{n-1}) + 5^{n-1}$
$\ldots$ and the results were close, but not exact.
Can anyone help me out with the correct method for solving these types of problems? Thanks very much for your time.
 A: This sequence is an affine recursion of the form $a_{n+1} = \lambda a_n + \mu$, with $\lambda=4\neq 1$ and $\mu=5$. Its $n$th term is given by
$$a_n = \lambda^n (a_0 - \rho) +\rho \, ,$$
where $\rho= \frac{\mu}{1-\lambda}$. The formula for the $n$th term can be obtained by setting $b_n = a_{n+1}-a_n$, which is a geometric sequence with common ratio $\lambda$,
$$
b_{n+1} = \underbrace{\lambda a_{n+1} + \mu}_{a_{n+2}} - \underbrace{(\lambda a_{n} + \mu)}_{a_{n+1}} = \lambda b_{n} \, ,
$$
and initial condition $$b_0 = a_1 - a_0 = \left(\lambda - 1\right) a_{0} + \mu \, .$$
The $n$th term $a_n$ is deduced from the telescoping series
\begin{aligned}
\sum_{k=0}^{n-1} b_k  = a_n - a_0 = b_0 \frac{1-\lambda^n}{1-\lambda} \, .
\end{aligned}
A: You have 
\begin{aligned}
a_n-4a_{n-1}&=5\\\\
4a_{n-1}-4^2a_{n-2}&=5\cdot4\\\\
4^2a_{n-2}-4^3a_{n-3}&=5\cdot4^2\\\vdots\\
4^{n-1}a_1-4^na_0&=5\cdot4^{n-1}
\end{aligned}
so
$a_n-4^na_0=5\sum\limits_{k=0}^{n-1}4^k=5\cdot\dfrac{4^n-1}{3}$
A: Finish the distributing the operators:
$$\begin{array} {rll}
%
a_0 &= 2 \\
%
a_1 &= 4\cdot 2 + 5 \\
%
a_2 &= 4\cdot (4\cdot 2 + 5) + 5 &= 4^2\cdot 2 + 4\cdot 5 + 5 \\
%
a_3 &= 4 \cdot (4^2\cdot 2 + 4\cdot 5 + 5) + 5 &=  4^3 \cdot 2 + 4^2\cdot 5 + 4 \cdot 5 + 5 \\
%
a_4 &= 4 \cdot (4^3 \cdot 2 + 4^2\cdot 5 + 4 \cdot 5 + 5) + 5 &=  4^4 \cdot 2 + 4^3 \cdot 5 + 4^2\cdot 5 + 4 \cdot 5 + 5 \\
%
\end{array}$$
Do you see the geometric series?  (Factor out the 5)
A: Such equations can be solved by 


*

*finding the general solution of the homogeneous equation $a_n=4a_{n-1}$; obviously $a_n=4^nc$.

*finding a particular solution of the non-homogeneous equation. Let us try the constant value $a$, and write
$$a=4a+5,$$
hence
$$a_n=a=-\frac53.$$
So the general solution is
$$a_n=4^nc-\frac53.$$
Now if we plug the initial condition,
$$a_0=2=4^0c-\frac53$$ so that $c=\dfrac{11}3$ and
$$a_n=\frac{11\cdot4^n-5}3.$$
A: Hint:
There is a general method for solving such affine recurrences:


*

*First search for a constant solution $c$: $\;c=4c+5\iff c=-\frac53$.

*Make the substitution $v_n=u_n-c=u_n+\frac53$. the recurrence relation becomes
$$v_n+c=4(v_{n-1}+c)+5\iff v_n=4v_{n-1}+3c+5=4v_{n-1}.$$
Therefore $(v_n)$ is a geometric sequence with common ratio $4$.

