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!

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.
