Finding the explicit formula for the recursion $a_n = 2a_{n-1} + a_{n-2}$ with $a_0 = 1$ and $a_1 = 3$?

Question

I'm trying to find the explicit formula for the recursion $a_n = 2a_{n-1} + a_{n-2}$ with $a_0 = 1$ and $a_1 = 3$. I already found the generating function: $f(x) = \frac{1+x}{1-2x-x^2}$, and the characteristic polynomial: $x^2 - 2x + 1 = 0$, which has the roots $1+√2$ and $1-√2$. What is the explicit formula for this recursion, and how do I find it?

Answer 1

Since the characteristic function has roots $1+\sqrt{2}$ and $1-\sqrt{2}$, the formula for the general term is $$a_n = A(1+\sqrt{2})^n+B(1-\sqrt{2})^n$$ for some constants $A$ and $B$.

Using the initial conditions $a_0 = 1$ and $a_1 = 3$, you get $$1 = a_0 = A+B$$ $$3 = a_1 = (1+\sqrt{2})A+(1-\sqrt{2})B$$ You simply need to solve this system of equations for $A$ and $B$.

In general, if the characteristic polynomial has distinct roots $r_1, r_2, \cdots, r_k$ each with multiplicity $1$, then the general term will be $a_n = C_1r_1^n+C_2r_2^n+\cdots+C_kr_k^n$.

If the roots $r_1,\ldots,r_n$ have multiplicities $m_1,\ldots,m_k$, then the formula is a bit more complicated: $a_n = p_1(n)r_1^n+\cdots+p_k(n)r_k^n$ where $p_i(n)$ is a polynomial with degree $\le m_i-1$.