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