How to solve this homogeneous recurrence relation of 2nd order?

Question

I have this homogeneous recurrence relation: $x_n = 3x_{n-1} + 2x_{n-2}$ for $n \geq 2$ and $x_0 = 0$, $x_1 = 1$. I form the characteristic polynomial: $r^2 - 3r -2 = 0$ which gives the roots $r = \frac{3}{2} - \frac{\sqrt{17}}{2}$, $\frac{3}{2} + \frac{\sqrt{17}}{2}$. Now when I pluck these values into the function $a_n = \alpha (\frac{3}{2} - \frac{\sqrt{17}}{2})^n + \beta (\frac{3}{2} + \frac{\sqrt{17}}{2})^n$ and solve it for $\alpha$ and $\beta$ I get enormous fractions which make my head hurt. Is there an easier and neater way of solving this or am I doing something wrong?

Answer 1

Name the roots $r$ and $s$ and solve for the initial conditions

$$ar^0+bs^0=0=a+b,\\ar^1+bs^1=1=ar+bs.$$

Then

$$a=-b=\frac1{r-s}.$$

The difference between the roots being $\sqrt{17}$, the "enormous fraction" is

$$x_n=\frac{\left(\frac{3+\sqrt{17}}2\right)^n-\left(\frac{3-\sqrt{17}}2\right)^n}{\sqrt{17}}=\frac{(3+\sqrt{17})^n-(3-\sqrt{17})^n}{2^n\sqrt{17}}.$$

Answer 2

Incidentally there is an easier way for quadratic recurrences (and no more).

Let $p,q$ be the two roots of the characteristic polynomial.

Then $x_{n+1} - p x_n = q ( x_n - p x_{n-1} ) = q^n ( x_1 - p x_0 )$.

And $x_{n+1} - q x_n = p ( x_n - q x_{n-1} ) = p^n ( x_1 - q x_0 )$.

Thus $(p-q) x_n = p^n ( x_1 - q x_0 ) - q^n ( x_1 - p x_0 )$.

Now you easily get the answer with the bare minimum computations necessary!

(Of course, this requires $p \ne q$, but usually if $p = q$ then they would be nice rational numbers.)