Let $a>3$ be an integer. Define a sequence $X$ as :
\begin{equation}
\begin{aligned}
x_1 & = 1\\
x_2 & = a-1\\
x_n & = (a-2)x_{n-1}-x_{n-2}, \ \ n\ge3
\end{aligned}
\end{equation} if $a$ is not a perfect square and
\begin{equation}
\begin{aligned}
x_1 & = 1\\
x_2 & = \sqrt{a} > 0\\
x_3 & =a-1\\
x_4 & =(a-2)\sqrt{a} > 0\\
x_{2n+1} & = (a-2)x_{2n-1}-x_{2n-3} , \ \ \ \ \ \ \ n\ge 2\\
x_{2n} & = (a-2)x_{2n-2}-x_{2n-4}, \ \ \ \ \ \ \ n\ge 3
\end{aligned}
\end{equation}
if $a$ is a perfect sqaure. From a maple output, it appears the terms of this sequence form a complete solution for $x$ in positive integers for the given diophantine equation $y^2=a(1+xy-x^2)$. How do we go about proving this i.e each term of sequence $X$ is a solution and that these are the only positive solutions. I tried mathematical induction but got stuck.
Best Answer
Here is the sketch of the solution via Vieta jumping.
Consider the substitution $u=x$, $v=y-x$. Note that the equation in this case can be rewritten in the following way $$ (u+v)^2=a(uv+1). $$ If $a>4$ (otherwise the equation will have only finitely many solutions), then we may suppose that $u,v>0$ (the corresponding solution of the initial equation will be $(x,y)=(u,u+v)$): if $v=0$, then $u=\sqrt{a}$ and if $v<0$, then the only possibility is $u=1$, $v=-1$.
Our equation might be rewritten as quadratic in $u$ (but remember that it's symmetric in $u,v$): $$ u^2-(a-2)v\cdot u+(v^2-a)=0. $$ Then the idea is to perform the Vieta jumping: if pair $(u,v)$ is a solution of the equation with $u>v$, then the pair $\left(\frac{v^2-a}{u},v\right)$ is also a solution (note that $\frac{v^2-a}{u}=(a-2)v-u\in\mathbb{Z}$). However, $\frac{v^2-a}{u}<\frac{v^2}{u}<v<u$, so the solution $\left(\frac{v^2-a}{u},v\right)$ is "smaller" than $(u,v)$ (with respect to the sum of coordinates, for example). Now we can do the same with the new solution if $\frac{v^2-a}{u}>0$ and etc.
At some point we must stop and it means that $\frac{v^2-a}{u}<0$ for some solution $(u,v)$ (if $v^2-a=0$, then we reached the solution $(0,\sqrt{a})$). Therefore, $\frac{v^2-a}{u}\le -1$ $$ 0=u^2-(a-2)v\cdot u+(v^2-a)\le u^2-(a-2)vu-u=u(u-(a-2)v-1), $$ so $u\ge (a-2)v+1$. Plugging this inequality to the initial equation we get $$ 0=u^2-(a-2)v\cdot u+(v^2-a)\ge(a-2)v+1+v^2-a=(v-1)^2+a(v-1), $$ so $v=1$ and $u=a-1$.
Conclusion. If $a$ is not a perfect square, then we can reach any positive integer solution via Vieta jumps starting from the $(a-1,1)$. Now if we write formulas for "jumping up", we will obtain your recurrence relations.