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.
Best Answer
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)