Recurrence relation for Pell's equation $x^2-2y^2=1$

Question

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

Answer 1

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.

Answer 2

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

Answer 3

You can find the general recurrence relationship here:

https://crypto.stanford.edu/pbc/notes/contfrac/pell.html