# 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$. – coffeemath Dec 23 '13 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? – jamaicanworm Dec 23 '13 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. – Will Jagy Dec 23 '13 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? – jamaicanworm Dec 23 '13 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),...$ – Will Jagy Dec 23 '13 at 5:30
@jamaicanworm, $x = (u-1)/ 2, y = v/3, z = w/3.$ – Will Jagy Dec 23 '13 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.

-

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

-