Consider the sequence defined by
$$
\begin{cases}
a_0=1\\
a_1=2\\
a_n=3a_{n-1}+4a_{n-2} & \text{if }n\ge 2
\end{cases}
.$$
Find a closed form for $a_n$.
I tried listing out examples, but I don't see any common pattern between them. All solutions are greatly appreciated.
Best Answer
For homogeneous linear recurrences of the form $a_n = \alpha a_{n-1}+\beta a_{n-2}$ look to the associated characteristic polynomial:
$$\chi(x)=x^2-\alpha x - \beta$$
In this case, we have the characteristic polynomial $x^2-3x-4$ which factors as $(x-4)(x+1)$
In the case that the roots are distinct, say $\lambda_1,\lambda_2$, the general solution will be of the form $a_n = c_1 \lambda_1^n + c_2\lambda_2^n$ for some constants $c_1$ and $c_2$ to be determined from the initial conditions.
In the case that the two roots are the same (i.e. $\lambda_1=\lambda_2$) then instead the general solution will be of the form $a_n = c_1\lambda^n + c_2n\lambda^n$
In our case, the roots are $4$ and $-1$ respectively so we see that our general solution will be of the form:
$$a_n = c_1 4^n + c_2(-1)^n$$
Now, we wish to find what values of $c_1$ and $c_2$ will work for this. We are told what $a_0$ and $a_1$ are, so using this information we have a system of two equations and two unknowns:
$$\begin{cases}a_0 = c_14^0 + c_2(-1)^0\\ a_1 = c_14^1 + c_2(-1)^1\end{cases}$$
Simplifying:
$$\begin{cases} 1 = c_1+c_2\\ 2=4c_1-c_2\end{cases}$$
Solving by first adding the two lines together, we have $5c_1=3$ implying $c_1=\frac{3}{5}$ further implying that $c_2=\frac{2}{5}$
This tells us the final closed form is:
$$a_n = \frac{3\cdot 4^n + 2(-1)^n}{5}$$
(the method above extends nicely as well to higher order linear recurrences as well as nonhomogeneous forms. most textbooks on the subject will have more information)