<s>[INST] Does this sequence consist of squares of integers? Question:

let  sequence $\{x_{n}\}$ such $$x_{0}=0,x_{1}=1,x_{2}=0,x_{3}=1$$
and such
  $$x_{n+3}=\dfrac{(n^2+n+1)(n+1)}{n}x_{n+2}+(n^2+n+1)x_{n+1}-\dfrac{n+1}{n}x_{n}$$
show that:$ x_{n}$ are all square number?

My idea: I have
$$x_{4}=3\cdot 2-2\cdot 1=4=2^2$$
$$x_{5}=\dfrac{21}{2}\cdot 4+(2^2+2+1)\cdot 1=49=7^2$$
and so on,but for all $n$,How prove it?
Thank you
 [/INST] In fact $x_{n+1}=a_n^2$, where $\{a_n\}$ are determined by the recurrence relation
$$a_{n+1}=n a_n+a_{n-1}$$
with the initial conditions $a_0=1$, $a_1=0$. This can be exprerimentally discovered using the online encyclopedia of integer sequences, and then the proof can be easily carried out by induction.
Proof: The only nontrivial induction step:
\begin{align}
x_{n+3}=\frac{(n^2+n+1)(n+1)}{n}a_{n+1}^2+(n^2+n+1)a_{n}^2-\frac{n+1}{n}a_{n-1}^2=\ldots=a_{n+2}^2,
\end{align}
where the dots denote expressing $a_n$ and $a_{n-1}$ in terms of $a_{n+2}$ and $a_{n+1}$. $\quad \blacksquare$
</s>