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?

It is correct. Do not forget to apply the conditions to get $\alpha,\beta$ — Claude Leibovici, Jun 10 '16 at 09:32
@ClaudeLeibovici: He doesn't like solving simultaneous equations with radicals flying around. See my answer for the best way I know to avoid that! — user21820, Jun 10 '16 at 09:39

score 2 · Accepted Answer · answered Jun 10 '16 at 10:13

2

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}}.$$

answered Jun 10 '16 at 10:13

Since $\frac{\sqrt{17}-3}{2}<1$, you could also take $x_n$ as the nearest integer to $\frac{(3+\sqrt{17})^n}{2^n\sqrt{17}}$. – almagest Jun 10 '16 at 10:33
@almagest: I know about this trick. Anyway, when you take the nearest integer, one can fear that the truncation error exceeds $\frac12$, so I guess that a safer criterion is $s^2<\frac12$. Or is there a safe justification ? – Jun 10 '16 at 11:14
It seems fairly safe here: $\frac{1}{\sqrt{17}}\left(\frac{\sqrt{17}-3}{2}\right)^n\approx0.24\times0.56^n$. – almagest Jun 10 '16 at 11:35
@almagest: obviously, but I am more after a criterion for the general case. – Jun 10 '16 at 11:53

score 1 · Answer 2 · answered Jun 10 '16 at 09:38

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.)

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

2 Answers2