# Linear recurrence solution to Diophantine equation

I have a Diophantine equation of the form: $$ax^2 + bx + c = y^2, \quad x, y \in \mathbb{Z^+}$$ Is it true that there will always be a linear recurrence formula that generates all the solutions for $x$, of the form: $$x_n = \alpha_1x_{n-1} + \alpha_2x_{n-2} + \alpha_3,$$ for some constants $\alpha_1, \alpha_2, \alpha_3 \in \mathbb{Z^+}$ (where plugging integers into $n$ generates the next $x$ that solves the Diophantine equation)?

If so, is it possible to prove this?

And if so, is it possible to show how these constants $\alpha_1, \alpha_2, \alpha_3$ are found?

• Such equations can often be turned into Pell type equations, on multiplying by some constant and completing the square. And many Pell equations have recurrences which go with them, though the simplest are pairs of recurrences each involving the previous $x$ and the previous $y$. Dec 23, 2013 at 2:32

I'm afraid this is overly optimistic. Multiplying through by $4a$ and completing the square, you go get a Pell type equation with some constant, and no more $b.$ The real problem is class number. The automorphism group of the Pell quadratic form is well behaved. However, there may be several seed values (pairs) rather than just two, and the rcurrence you describe takes you from one, well, fundamental region (cycle in Conway's topograph 'river') to the next. Read the first chapter in his Sensual Quadratic Form book and ask him about it.

I drew several topograph pictures for MSE answers, two are at Generate solutions of Quadratic Diophantine Equation . I drew on graph paper so the river is a perfectly straight line. That's life.

• I'm most curious in my UPDATE to this question: math.stackexchange.com/q/611135/23390 It seems like I found recurrences that work for the 2 Diophantine equations I described, but how can I be sure they are correct? Dec 23, 2013 at 2:46
• @jamaicanworm, the part that can be proved is this: given an indefinite quadratic form $a x^2 + b x y + c y^2,$ homogeneous!!, with $b^2 - 4 a c > 0$ but not a square, all pairs $(x,y)$ satisfying $a x^2 + b x y + c y^2 = d$ can be described by the methods I describe. Getting the quadratic form is up to you. See Conway's little book, also Binary Quadratic Forms by Buell, same title by Buchmann and Vollmer. Dec 23, 2013 at 2:54
• Thank you for the explanation! In the linked problem, I can combine the system of two Diophantine equations to get one of the form $\frac{4}{9}x^2 + \frac{4}{9}x = z^2 - y^2$. This now has 3 variables--is there a way to prove that a solution does or does not exist? Dec 23, 2013 at 4:59
• @jamaicanworm, yes, infinitely many. $u^2 + v^2 - w^2 = 1$ with $u$ odd, $v,w$ divisible by $3.$ So, $(1,3,3),$ then $(71,69,99), (2377, 2379, 3363),...$ Dec 23, 2013 at 5:30
• @jamaicanworm, $x = (u-1)/ 2, y = v/3, z = w/3.$ Dec 23, 2013 at 5:41

$Y^2=aX^2+bX+1$

Using solutions of Pell's equation: $p^2-as^2=1$

Solutions can be expressed through them is quite simple.

$Y=p^2+bps+as^2$

$X=2ps+bs^2$

$p,s$ - can be any character.

• This solution can’t be correct. Here’s a counterexample: set $(a,b)=(22,13)$, so that a solution to the quadratic form is $(x,y)=(1,6)$, because $$6^2 = 22(1^2)+13(1)+1.$$ But there are no integers $p,s$ satisfying \begin{align}6 &= p^2+13ps+22s^2\\ 1&=2ps+13s^2\end{align}. Nov 30, 2017 at 6:31
• @KierenMacMillan there is a single Pell equation. You can in fact be reduced. For Your case. $p^2-22s^2=3$ $$Y^2=22X^2+13X+1$$ $p=-5$ ; $s=1$ $$Y=\frac{1}{3}((-5)^2-13*5*1+22*1^2)=-6$$ $$X=\frac{1}{3}(1(13*1-2*5*1))=1$$ Nov 30, 2017 at 8:36
• Is there a solution with $y=6$ (not $y=-6$)? Nov 30, 2017 at 14:55

Though it is necessary to bring the decisions some pretty simple solutions:

the equation: $aX^2+bXY+cY^2=f$

If the root of the whole: $\sqrt{\frac{f}{a+b+c}}$

Then use the solution of Pell's equation: $p^2-(b^2-4ac)s^2=1$

Solutions can be written:

$Y=((4a+2b)ps\pm(p^2+(b^2-4ac)s^2))\sqrt{\frac{f}{a+b+c}}$

$X=(-(4c+2b)ps\pm(p^2+(b^2-4ac)s^2))\sqrt{\frac{f}{a+b+c}}$

If a root: $\sqrt{fa}$ then the solutions are of the form:

$Y=4ps\sqrt{fa}$

$X=(-2bps\pm(p^2+(b^2-4ac)s^2))\sqrt{\frac{f}{a}}$

Although it should be mentioned, and the equation: $aX^2-qY^2=f$

If the root of the whole: $\sqrt{\frac{f}{a-q}}$

Using equation Pell: $p^2-aqs^2=1$ solutions can be written:

$Y=(2aps\pm(p^2+aqs^2))\sqrt{\frac{f}{a-q}}$

$X=(2qps\pm(p^2+aqs^2))\sqrt{\frac{f}{a-q}}$

And for that decision have to find double formula.

$Y_2=Y+2as(qsY-pX)$

$X_2=X+2p(qsY-pX)$