Proof that $x^2 - 2y^2 = -1$ has a recurring solution for $x$

Question

I read here about the following variation on Pell's equation: $$ x^2 - 2y^2 = -1.$$

According to Dario Alpern's solver, the equation has infinite integer solutions, which can be generated by the recursion: $$x_n = 3x_{n-1} + 4y_{n-1},\\ y_n = 2x_{n-1} + 3y_{n-1}.$$

I'm only interested in solutions for $x$. According to the Online Encyclopedia of Integer Sequences, it appears (by plugging in the first few values of $x_n$ from the above), that the sequence can be written as the following linear recurrence: $$x_n = 6x_{n-1} - x_{n-2}.$$

Question: Is there proof that the solutions for $x$ can be written as a $2$-deep linear recurrence (without using the above formula for $x$ and $y$ from the solver)? If the answer is long and involved, a reference to a well-explained proof would suffice.

Answer 1

I recommend at least two books, Binary Quadratic Forms by Duncan A. Buell, and Binary Quadratic Forms by Buchmann and Vollmer. Buell is better at explaining.

Given some $n,$ which is $2$ in your case, we find the smallest solution to $$ u^2 - n v^2 = 1 $$ with both $u,v > 0.$ The fact that there is always a nontrivial solution takes several steps.

We get the generator of the automorphism group, $$ A = \left( \begin{array}{cc} u & nv \\ v & u \end{array}\right). $$ The eigenvalues are $\lambda = u + v \sqrt n$ and $1/\lambda = u - v \sqrt n,$ and they satisfy $$ \lambda^2 - 2 u \lambda + 1 = 0. $$ Divide through by $\lambda^2$ to confirm that $$ \frac{1}{\lambda^2} - 2 u \frac{1}{\lambda} + 1 = 0. $$ The eigenvectors are $$ \left( \begin{array}{c} \sqrt n \\ 1 \end{array}\right), \left( \begin{array}{c} - \sqrt n \\ 1 \end{array}\right). $$ These are not orthogonal, but they are a basis of the vector space $\mathbb R^2.$ Any column vector $$ \left( \begin{array}{c} x \\ y \end{array}\right) $$ can be written as a linear combination of those two. Easy enough to check, $$ A^2 - 2 u A + I = 0. $$ So, if $$ w = \left( \begin{array}{c} x_j \\ y_j \end{array}\right), \; \; A w = \left( \begin{array}{c} x_{j+1} \\ y_{j+1} \end{array}\right), \; \; A^2 w = \left( \begin{array}{c} x_{j+2} \\ y_{j+2} \end{array}\right), $$ we find $$ A^2 w = 2 u A w - w, $$ and your recurrence follows.

You can also confirm easily enough that $$ x_{j+2}^2 - n y_{j+2}^2 = x_{j+1}^2 - n y_{j+1}^2 = x_{j}^2 - n y_{j}^2. $$

If your $ x_{j}^2 - n y_{j}^2$ were anything other than $\pm 1,$ there would be a problem at exactly this point, because it is not the case in general that all solutions to a Pell variant, with other right hand side, is in the automorphism orbit of a single seed vector. However, as you have $x^2 - n y^2 = -1,$ it follows, after quite a bit of detail, that there is only one orbit: all solutions happen this way, allowing negative entries changes nothing and so on. Notice also that when we do have $x^2 - n y^2 = -1$ with minimal positive $x,y,$ it follows that $$ u = x^2 + n y^2, \; \; \; v = 2 x y. $$

Thursday. It may help to point out that, for some problem $x^2 - n y^2 = k,$ the formalism above gives a finite set of sequences $(x_j,y_j)$ of solutions that do satisfy the degree two recurrence. It is just that, if you put all the $x$ values in order, the effect is of mixing the sequences together, the indexing is thrown off, and you can no longer see these relationships. But, if you know what is going on, it is easy enough to pull out a finite set of seed values for $x.$ This would happen, for instance, in solving $$ x^2 - 2 y^2 = 119 = 7 \cdot 17 . $$ This naturally splits into four sequences of solutions, $$ (11,1); \; (37,25); \; (211,149); \; (1229,869); \ldots $$ $$ (13,5); \; (59,41); \; (341,241); \; (1987,1405); \ldots $$ $$ (19,11); \; (101,71); \; (587,415); \; (3421,2419); \ldots $$ $$ (29,19); \; (163,115); \; (949,671); \; (5531,3911); \ldots $$ If you put all the $x$ values in order, $$ 11,13,19,29,37,59,101,163,211,341,587,949,1229,1987,3421,5531,\ldots $$ you do get $$ x_{j + 8} = 6 x_{j+4} - x_j. $$

Answer 2

Problems like this is best handled using z-transform. I find it easier to work with $z$ which is the unit advance operator, i.e. increases the subscript by $1$

We can rewrite the original recurrence as (where it us customary to use upper case letters) $$ z X= 3 X + 4Y,\\ z Y = 2X + 3Y. $$ Eliminate $Y$ and isolate the highest power of $z$: $$ z^2 X - 6 z X + X = 0 ~\Rightarrow z^2 X = 6 z X -X$$

Now that $z$ has done its part, use the fact that $z$ advances the index by $1$ and $z^2$ by 2 to get $$ z^2 X = 6 z X -X \Rightarrow x_{n+2} = 6 x_{n+1} - x_n$$

If you want to write in terms of indices before $n$ then go back and divide the last equation by $z^2$ to get $$X = 6 z^{-1} X - z^{-2} X$$ or $$ X = 6 z^{-1} X - z^{-2} X \Rightarrow x_n = 6 x_{n-1} -x_{n-2}$$

It is a matter of taste to work with $z$ or $z^{-1}$. I personally prefer $z$ till the very end. The above procedure works for any coupled linear recurrence relationship in any number of variables. Only algebra gets messier

Answer 3

Let me see if I can show you how to discover the recurrence formula without using continued fraction. To do this you have to assume that a linear recurrence exists and you try and discover it.

Now let $$ J = \begin{bmatrix}1 & 0\cr 0 & -2\end{bmatrix}$$ Then the original equation is $$ \begin{bmatrix}x & y\end{bmatrix}\, J \,\begin{bmatrix}x \\ y\end{bmatrix}=-1$$

Assume that there is a recurrence relationship $$ \begin{bmatrix}x_n \\ y_n\end{bmatrix}= \begin{bmatrix}\alpha& \beta\cr \gamma & \delta\end{bmatrix}\begin{bmatrix}x_{n-1}\\ y_{n-1}\end{bmatrix}$$ To satisfy the original equation we need $$ \begin{bmatrix}\alpha& \beta\cr \gamma & \delta\end{bmatrix}^{T} \begin{bmatrix}1 & 0\cr 0 & -2\end{bmatrix} \begin{bmatrix}\alpha& \beta\cr \gamma & \delta\end{bmatrix} = \begin{bmatrix}1 & 0\cr 0 & -2\end{bmatrix} $$

If you multiply it out to get 4 equations. You will end up with another Pellian equation of the same form. All you need is one solution with the smallest value for the $\alpha$, $\beta$, $\gamma$ and $\delta$.

You will get the equations: $$ \beta^2 - 2 \alpha^2 = 2$$ The smallest solution is $\alpha =3$, $\beta=4$.

The other equation you need is $$ \delta^2-2\gamma^2=1$$ $\delta=3$, $\gamma=2$ is clearly the smallest solution.