3
$\begingroup$

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

Improve this question
$\endgroup$
  • $\begingroup$ For adding more details, it is recommended that you edit your question instead of creating a comment. Thanks. $\endgroup$ – GoodDeeds Sep 27 '18 at 7:03
  • $\begingroup$ Thanks. I will edit the question. $\endgroup$ – Kai Sep 27 '18 at 7:04
  • 1
    $\begingroup$ I'm not familiar with this particular technique, but it's easy to see that $x_n = 6x_{n-1} - x_{n-2}$ satisfies the formula given. It's also not difficult to see that it is the only recurrence relation of the form $x_n = ax_{n-1} + bx_{n-2}$ that the formula satisfies. If you are looking for such a recurrence relation, you've found it! $\endgroup$ – Theo Bendit Sep 27 '18 at 7:17
  • $\begingroup$ I haven't learned generating functions, so I don't quite understand why it works, and why it is the only formula that work. I will try to figure that out. $\endgroup$ – Kai Sep 27 '18 at 7:25
  • $\begingroup$ Have you tried to expand the formula $x_{n+1}=6 x_n - 1 x_{n-1}$ using the fractional/exponential expression that you already have, simplify and identify the correctness of the recursion-formula? $\endgroup$ – Gottfried Helms Sep 27 '18 at 7:30
3
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Note also that you can show that the recurrence is true simply by showing that it works for the general term you have. This answer shows you how to derive it. $\endgroup$ – Mark Bennet Sep 27 '18 at 7:39
1
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ Is this group theory? $\endgroup$ – Kai Sep 28 '18 at 3:24
  • $\begingroup$ @Kai the only group theory you need for this is how to multiply 2 by 2 integer matrices of determinant $1$ $\endgroup$ – Will Jagy Sep 28 '18 at 3:28
-1
$\begingroup$

You can find the general recurrence relationship here:

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.