<s>[INST] general solution for a recurrence relation 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.
 [/INST] 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)
$$
</s>