Solving a Recurrence Relation $3a_{n-1} - 4$

Question

Suppose you have the recurrence relation:

$a_n = 3a_{n-1}-4$

$a_0 = 8$

I am confident I have figured out the pattern, but I am unable to write in a closed form.

$$a_n = 3a_{n-1}-4$$ $$= 3(3a_{n-2} - 4) - 4 = 3 *3 a_{n-2} - 3*4 -4$$ $$= 3(3(3(a_{n-3}-4)-4)-4 = 3*3*3a_{n-3} - 3*3*4 - 3*4 - 4$$

Clearly, the closed form solution must contain $3^n*8$, and a term subtracting $4$ in batches of $3$ with the number of $3$s decreasing.

Any ideas?

Answer 1

Use $$a_{n}-2=3(a_{n-1}-2).$$

Thus, since $a_n-2$ is a geometric progression, we obtain: $$a_n-2=(8-2)3^n$$

Answer 2

$a_n-3a_{n-1}=-4$

$a_{n-1}-3a_{n-2}=-4$

Subtract to get the homogeneous recurrence

$a_n-4a_{n-1}+3a_{n-2}=0$

with characteristic equation $x^2-4x+3$, which has roots $1$ and $3$.

Therefore, $a_n=b3^n+c1^n$.

Use knowledge of $a_0$ and $a_1$ to solve for $b$ and $c$.

Answer 3

You could solve it by finding the characteristic equation.

Given

$$a_n=3a_{n-1}-4$$

you can write this without a constant by subtracting

$$a_{n-1}=3a_{n-2}-4$$

to get

$$a_n=4a_{n-1}-3a_{n-2}$$

Now to find the characteristic equation substitute $r^n$ for $a_n$

$$r^n=4r^{n-1}-3r^{n-2}$$

which is equal to

$$r^{n-2}(r^2-4r+3)=0$$

Solving this equation, r equals 3 or 1 and so the characteristic equation is

$$a_n=p3^n+q$$

where p,q are real numbers Since $a_0=8$ and $a_1=20$

$$8=p+q$$

$$20=3p+q$$

Solving this system of equations shows that $p=6$ and $q=2$ Therefore, the answer is

$$a_n=6*3^n+2$$

Answer 4

A small trick for any linear recurrence relation.

Making the problem more general , consider $$a_n = \alpha\, a_{n-1}+\beta$$ Let $a_n=b_n+k$ and replace $$b_n+k=\alpha\, b_{n-1} +\alpha\, k+\beta$$ Make $$k=\alpha\, k+\beta \implies k=\frac \beta {1-\alpha}\implies b_n=\alpha\, b_{n-1} $$ Solve it for $b_n$ (this is simple) and $a_n=b_n+k$.