general solution for a recurrence relation

Question

I have the following recurrence relation: $$x_1=1, x_2=a, x_{n+2}=ax_{n+1}-x_n\hspace{1cm}(*)$$

If we assume that $x_n=r^n$ is a solution for the relation $x_{n+2}=ax_{n+1}-x_n$, then I can deduce that $r=\frac{a+\sqrt{a^2-4}}{2}$ or $r=\frac{a-\sqrt{a^2-4}}{2}$.

By using the initial values $x_1=1, x_2=a$, I found that $$x_n=\frac{1}{\sqrt{a^2-4}}\left(\frac{a+\sqrt{a^2-4}}{2}\right)^n-\frac{1}{\sqrt{a^2-4}}\left(\frac{a-\sqrt{a^2-4}}{2}\right)^n$$ is a solution for the recurrence relation (*).

Question: How do we know whether this is the only solution for the recurrence relation $(*)$? Notice that when I found the particular solution above I assumed that the solution was a linear combination of geometric series. But I do not know if all the solutions will have this form.

Answer 1

You have specific initial values $x_0$ and $x_1$. The recurrence relation fully determines all other values. Thus, there's exactly one solution. If you've found it, that's it, there can't be any others, no matter what approach you took in order to find it.

If you want to show that all solutions of $x_{n+2}=ax_{n+1}-x_n$ are combinations of the geometric series you found, you can argue as follows:

This is a linear second-order recurrence. Its solutions form a two-dimensional vector space. (A vector space because of the linearity of the recurrence, and a two-dimensional one because the solution space is spanned by the two solutions for the initial conditions $x_1=1$, $x_2=0$ and $x_1=0$, $x_2=1$.) You've found two linearly independent solutions; hence they span the entire solution space.

Answer 2

A bit of culture. Any two consecutive numbers in your sequence, call them $x_n$ and $x_{n+1},$ satisfy $$ x_n^2 - a \, x_n \, x_{n+1} + x_{n+1}^2 = 1 $$

Try consecutive values in $$ 1, \; \; a, \; \; a^2 - 1, \; \; a^3 - 2a, \; \ldots $$

This comes from the matrix $$ \left( \begin{array}{cc} 0 & 1 \\ -1 & a \end{array} \right) $$ which has determinant $1$ and trace $a.$ It also gives an automorphism of the quadratic form $x^2 - a xy+y^2.$ An automorphism matrix $P$ for a quadratic form that has Hessian matrix $H$ satisfies $P^T HP = H$

In this case $$ \left( \begin{array}{cc} 0 & -1 \\ 1 & a \end{array} \right) \left( \begin{array}{cc} 2 & -a \\ -a & 2 \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ -1 & a \end{array} \right) = \left( \begin{array}{cc} 2 & -a \\ -a & 2 \end{array} \right) $$

The explicit relation with the sequence is

$$ \left( \begin{array}{cc} 0 & 1 \\ -1 & a \end{array} \right) \left( \begin{array}{c} x_n \\ x_{n+1} \end{array} \right) = \left( \begin{array}{c} x_{n+1} \\ x_{n+2} \end{array} \right) $$