<s>[INST] Recurrence relation for Pell's equation $x^2-2y^2=1$ I am wondering how to find the recurrence relation for solutions for $x$ in the Pell's equation $x^2-2y^2=1$.
I know the formula for the general term.
It is $$\frac{(3+2\sqrt2)^n+(3-2\sqrt2)^n}{2}$$ for $x_n$, the $n^{th}$ smallest solution for $x$.
Any help would be appreciated! Thanks!
I got a feeling that the recurrence formula is $x_n=6x_{n-1}-x_{n-2}$, but I wonder how to prove this relation true/false and how to derive/generate the recurrence relation.
Note that $x_{-1}=1$ and this recurrence formula applies to all nonnegative integral $n$.
 [/INST] The fundamental solution is $9-8 = 1,$ meaning $3^2 - 2 \cdot 2^2 = 1.$ As a result, we have the matrix
$$
A =
\left(
\begin{array}{cc}
3 & 4 \\
2 &3
\end{array}
\right)
$$
which solves the automorphism relation, $A^T H A = H,$ where
$$
H =
\left(
\begin{array}{cc}
1 & 0 \\
0 & -2
\end{array}
\right)
$$
That is
$$ (3x+4y)^2 - 2 (2x+3y)^2 = x^2 - 2 y^2.  $$
Next,
$$ A^2 - 6 A + I = 0. $$
Since
$$
A
\left(
\begin{array}{c}
x_n \\
y_n
\end{array}
\right) =
\left(
\begin{array}{c}
x_{n+1} \\
y_{n+1}
\end{array}
\right)
$$
and
$$
A^2
\left(
\begin{array}{c}
x_n \\
y_n
\end{array}
\right) =
\left(
\begin{array}{c}
x_{n+2} \\
y_{n+2}
\end{array}
\right)
$$
we find
$$ x_{n+2} - 6 x_{n+1} + x_n = 0  $$
$$ y_{n+2} - 6 y_{n+1} + y_n = 0  $$
This is just Cayley-Hamilton.
Caution: This is for $x^2 - 2 y^2 = 1.$ If we change the problem to $x^2 - 2 y^2 = 119 = 7 \cdot 17,$ the recurrence still holds, except that there are now  four such families, each using the same recursion:
$$ (11,1) \; \; \; \; (37,25) \; \; \; \; (211,149) ... $$
$$ (13,5) \; \; \; \; (59,41) \; \; \; \; (341,241) ... $$
$$ (19,11) \; \; \; \; (101,71) \; \; \; \; (587,415) ... $$
$$ (29,19) \; \; \; \; (163,115) \; \; \; \; (949,671) ... $$
If you don't mind negative values for $x,y$ you can combine the above four into two families going both forth and back...
</s>