Closed form expression of the nth term

Question

We have to find the closed form of the nth term of the recurrence relation:$$a_n = 2 a_{n-1} + a_{n-2}$$ $\forall n > 1$ It is given that $a_0 = 0, a_1 = 1$

---

I got the characteristics equation to be $x^2-2x-1=0$ and it has $2$ roots $1\pm √2$. But do I get a closed form expression of $a_n$ from this?

Answer 1

There is actually a nice rule that states that if the roots to the characteristic equation are $\alpha$ and $\beta$, then $$a_n=A\alpha^n+B\beta^n$$ is the closed form expression to the sequence. So in your case, $\alpha=1+\sqrt2$ and $\beta=1-\sqrt2$. All it remains is to substitute the values we were given to find $A$ and $B$. $$a_0=0=A(1+\sqrt2)^0+B(1-\sqrt2)^0$$ $$\implies 0=A+B$$ and $$a_1=1=A(1+\sqrt2)^1+B(1-\sqrt2)^1$$ $$\implies1=A+B+\sqrt2A-\sqrt2B$$ $$\implies1=\sqrt2A-\sqrt2B$$

Solving the two simultaneous equations for $A$, $B$ we have $$A=\frac{1}{2\sqrt2}$$ $$B=-\frac{1}{2\sqrt2}$$

in other words, substituting these values of $A$ and $B$ back we have $$a_n=\frac{(1+\sqrt2)^n}{2\sqrt2}-\frac{(1-\sqrt2)^n}{2\sqrt2}$$ which is the closed form expression for this sequence. Hope this helped.

Answer 2

You can write $$\left( \begin{matrix} {{a}_{n+1}} \\ {{a}_{n}} \\ \end{matrix} \right)=\left( \begin{matrix} 2 & 1 \\ 1 & 0 \\ \end{matrix} \right)\left( \begin{matrix} {{a}_{n}} \\ {{a}_{n-1}} \\ \end{matrix} \right)$$

The eigenvalues of this matrix M are the roots of your characteristic equation. The matrix can be diagonalized in the form $M = UDU^{-1}$ where D is diagonal with entries the 2 eigenvalues and U has columns which are the corresponding eigenvectors. Then $M^n = UD^nU^{-1}$ and

$$\left( \begin{matrix} {{a}_{n+1}} \\ {{a}_{n}} \\ \end{matrix} \right)=UD^nU^{-1} \left( \begin{matrix} {{a}_{1}} \\ {{a}_{0}} \\ \end{matrix} \right)$$

from which $a_n$ can be read off.