Sequence in which adding 2 produces a square

We have \begin{align*} x_{n+1}+x_{n-2}&=x_{n}x_{n-1}\\ \end{align*} then \begin{align*} x_{n+1}x_{n-2}&=x_{n}x_{n-1}x_{n-2}-x_{n-2}^2\\ &=x_n(x_{n}+x_{n-3})-x_{n-2}^2\\ &=x_nx_{n-3}+x_{n}^2-x_{n-2}^2\\ \end{align*} then by telescoping \begin{align*} x_{n+1}x_{n-2}&=x_4x_1+x_n^2+x_{n-1}^2-x_3^2-x_2^2\\ x_{n+1}x_{n-2}&=x_n^2+x_{n-1}^2-4\\ \end{align*} Now we let $x_n=z_n-2$. We then have

\begin{align*} z_{n+1}z_{n-2}-2z_{n+1}-2z_{n-2}+4&=z_n^2-4z_n+4+z_{n-1}^2-4z_{n-1}+4-4\\ z_{n+1}z_{n-2}&= z_n^2-4z_n+z_{n-1}^2-4z_{n-1}+2z_{n+1}+2z_{n-2}\\ z_{n+1}z_{n-2}&= z_n^2-4z_n+z_{n-1}^2-4z_{n-1}+2x_{n+1}+4+2z_{n-2}\\ \end{align*} But \begin{align*} x_{n+1}&=x_nx_{n-1}-x_{n-2}\\ &=(z_n-2)(z_{n-1}-2)-z_{n-2}+2 \end{align*} then by substitution and reduction, we find \begin{align*} z_{n+1}z_{n-2}&=(z_n+z_{n-1}-4)^2 \end{align*} from which a proof by induction easily follows.

Addition We show that $v_n=\sqrt{\frac{x_{n}-2}{5}}$ is A101361 (shifted).

We have $z_n = 5v_n^2+4$ and $x_n= 5v_n^2+2$. Then \begin{align*} z_{n+1}z_{n-2}&=(z_n+z_{n-1}+4)^2\\ (5v_{n+1}^2+4)(5v_{n-2}^2+4)&=(5v_{n}^2+5v_{n-1}^2+4)^2 \end{align*} which, after algebric manipulations, can be rearranged as $$5v_{n+1}^2v_{n-2}^2-5(v_{n}^2-v_{n-1}^2)=4\left(5v_{n}^2v_{n-1}^2 +2v_n^2 +2v_{n-1}^2 -(v_{n+1}^2+v_{n-2}^2)\right) \tag1 $$ On the other hand, we have \begin{align*} x_{n+1}+x_{n-2}&=x_nx_{n-1}\\ 5v_{n+1}^2+2+5v_{n-2}^2+2&=(5v_{n}^2+2)(5v_{n-1}^2+2) \end{align*} which can be simplified so that $$v_{n+1}^2+v_{n-2}^2 = 5v_{n}^2v_{n-1}^2 +2v_n^2 +2v_{n-1}^2 \tag2$$ Comparing (1) and (2), we see that it must be that $v_{n+1}v_{n-2}=v_n^2 - v_{n-1}^2$ which is the third-order nonlinear recursion that is satisfied by A101361. Moreover, it is easy to verify that the initial terms are equal (shifted). Also it is said in that OEIS page that $v_{n+1}= F_{2F_{n}}$, where $F_{n}$ is the Fibonacci number. Then we finally obtain a nice closed form for the OP sequence, in terms of Fibonacci and Lucas numbers:

$$ x_n = L_{2F_{n-1}}^2 -2$$