<s>[INST] Bulgarian Mathematical Olympiad 1987 The sequence $x_1,x_2,\dots$ is defined by the equalities $x_1=x_2=1$ and $$x_{n+2}=14x_{n+1}-x_n-4, n\geq 1$$
Prove that each number of the given sequence is a perfect square.

I used the standard way to solve recurrence relations and arrived at
$$x_n=\frac{1}{6}\bigg( (2+\sqrt{3})^{n-\frac{3}{2}} + (2-\sqrt{3})^{n-\frac{3}{2}} \bigg)^2$$
which I think should be quite close. Any idea how to proceed?
 [/INST] The equation is equivalent to
$$
x_{n+2}-14x_{n+1}+x_n=-4\tag1
$$
which is the same as
$$
\left(x_{n+2}-\tfrac13\right)-14\left(x_{n+1}-\tfrac13\right)+\left(x_n-\tfrac13\right)=0\tag2
$$
Using the standard methods for Linear Difference Equations, we note that
$$
x^2-14x+1=0\tag3
$$
has roots $7+4\sqrt3$ and $7-4\sqrt3$, so that $(2)$ has solutions
$$
x_n=\tfrac13+c_1\left(7+4\sqrt3\right)^{n-1}+c_2\left(7-4\sqrt3\right)^{n-1}\tag4
$$
Since $x_1=x_2=1$, we get
$$
\begin{align}
x_n
&=\tfrac13+\tfrac{2-\sqrt3}6\left(7+4\sqrt3\right)^{n-1}+\tfrac{2+\sqrt3}6\left(7-4\sqrt3\right)^{n-1}\\[3pt]
&=\tfrac13+\tfrac{2-\sqrt3}6\left(2+\sqrt3\right)^{2n-2}+\tfrac{2+\sqrt3}6\left(2-\sqrt3\right)^{2n-2}\\
&=\left(\tfrac{\sqrt3-1}{2\sqrt3}\left(2+\sqrt3\right)^{n-1}+\tfrac{\sqrt3+1}{2\sqrt3}\left(2-\sqrt3\right)^{n-1}\right)^2\\[3pt]
&=u_n^2\tag5
\end{align}
$$
Since $2+\sqrt3$ and $2-\sqrt3$ are roots of
$$
u^2-4u+1=0\tag6
$$
we have $u_1=u_2=1$ and
$$
u_n=4u_{n-1}-u_{n-2}\tag7
$$
Therefore, $u_n\in\mathbb{Z}$ and $x_n=u_n^2$.

For example, using $(7)$
$$
\{u_n\}=\{1,1,3,11,41,153,571,\dots\}\tag8
$$
and using $(1)$
$$
\{x_n\}=\{1,1,9,121,1681,23409,326041,\dots\}\tag9
$$
</s>