Show that for every $n$ there are integers $a,b$ such that $X_n = a^2 + 2b^2$ We have a sequence $X_0, X_1,...$ which is determined by $X_0=1, X_1=3$ and $X_n = 6X_{n-1} - X_{n-2}$
Show that for every $n$ there are integers $a,b$ such that
$X_n = a^2 + 2b^2$
I thought of changing $a^2 + 2b^2 = (a + \sqrt 2 i)(a - \sqrt 2 i)$, since I thought it might lead to something good, but I'm not getting anything.
Any hints or solutions are appreciated!
 A: Factoring the sum in the complex numbers does not seem to lead us anywhere. Neither does the knowledge of which integers in general can be represented as $a^2+2b^2$. We must try something else.
Well, the roots of the characteristic polynomial are $3\pm2\sqrt2$, which are obviously the squares of $1\pm\sqrt2$, which are related to Pell numbers, hence so must be our $a,b$ - this was my reasoning, about as vague as it gets.
Indeed, for the sequence defined by $P_0=0,\;P_1=1,\;P_n=2P_{n-1}+P_{n-2}$ we have that $P_n+P_{n-1}$ and $P_n$ (which are, coincidentally, numerators and denominators of the best rational approximations to $\sqrt2$) work as $a$ and $b$ for our $X_n$.
$$\begin{array}{l|l|l|l|l|l|l}
n             & 0  & 1& 2&  3&  4&  5& \dots\\ \hline
P_n=b         & 0  & 1& 2& 5 & 12& 29& \dots\\ 
P_n+P_{n-1}=a & 1  & 1& 3& 7 & 17& 41& \dots\\
X_n=a^2+2b^2  & 1  & 3&17& 99&577&3363& \dots\\ \hline
\end{array}$$
The actual proof never bothered me. It should be easy to do by induction.
So it goes.
A: Let $(a_n,b_n)$ be solutions to Pell's equation $a_n^2-2b_n^2=\pm1$.
The fundamental solution is $1^2-2\times1=(1+\sqrt2)(1-\sqrt2)=-1$,
so solutions are $a_n^2-2b_n^2=(a_n+\sqrt2b)(a_n-\sqrt2b)=(1+\sqrt2)^n(1-\sqrt2)^n=(-1)^n$, where
$a_n+\sqrt2b_n=(1+\sqrt2)^n=(a_{n-1}+\sqrt2b_{n-1})(1+\sqrt2)=(a_{n-1}+2b_{n-1})+(a_{n-1}+b_{n-1})\sqrt2$,
so $$a_n=a_{n-1}+2b_{n-1}\tag1$$ and $$b_n=a_{n-1}+b_{n-1}\tag2$$.
Solutions to $X_n^2-2Y_n^2=1$ are given by $X_n+\sqrt2Y_n=(1+\sqrt2)^{2n}=a_{2n}+\sqrt2b_{2n}$
$=[(1+2\sqrt2)^n]^2=(a_n+\sqrt2b_n)^2=a_n^2+2b_n^2+2a_nb_n\sqrt2$,
so $X_n=a_n^2+2b_n^2=a_{2n}$ (and $Y_n=2a_nb_n=b_{2n}$).
From (1)-(2) we have $b_{n-1}=a_n-b_n=b_n-a_{n-1}$, so $a_n+a_{n-1}=2b_{n}$,
so $a_n=a_{n-1}+2b_{n-1}=a_{n-1}+(a_{n-1}+a_{n-2})=2a_{n-1}+a_{n-2}$.  Therefore,
$a_n=2(2a_{n-2}+a_{n-3})+a_{n-2}=5a_{n-2}+2a_{n-3}=5a_{n-2}+(a_{n-2}-a_{n-4})=6a_{n-2}-a_{n-4}$,
so $a_{2n}=6a_{2(n-1)}-a_{2(n-2)}$, so $X_n=6X_{n-1}-X_{n-2}$, and $X_n$ matches your sequence.
