Finding the closed form for a recurrence relation

Question

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.

Answer 1

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)

Answer 2

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}

Answer 3

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}$

Answer 4

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.$$

Answer 5

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$.