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$.
 A: If $u_n=A\alpha^n+B\beta^n$ then $\alpha$ and $\beta$ are the roots of the quadratic equation $$(x-\alpha)(x-\beta)=x^2-(\alpha+\beta)x+\alpha\beta=0$$
Let the quadratic be $p(x)=x^2-px+q$, then consider $$0=A\alpha^np(\alpha)+B\beta^np(\beta)=$$$$=(A\alpha^{n+2}+B\beta^{n+2})-p(A\alpha^{n+1}+B\beta^{n+1})+q(A\alpha^{n}+B\beta^{n})=u_{n+2}-pu_{n+1}+qu_n$$from which $$u_{n+2}=pu_{n+1}-qu_n$$Where $p=\alpha+\beta$ and $q=\alpha\beta$
You simply need to identify $\alpha$ and $\beta$ - the surrounding constants drop out in the arithmetic.
Once two successive terms are known, the constants $A$ and $B$ are determined, and there is a unique recurrence of this kind because two consecutive terms determine the rest through the recurrence.
A: 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...
A: You can find the general recurrence relationship here:
https://crypto.stanford.edu/pbc/notes/contfrac/pell.html
