MathNet 2000 — Math Olympiad Vault Question 18

Let $x_{1} = x_{2} = 1$ and $x_{n+2} = 2 x_{n+1} + 8 x_{n} - 1$ for $n \geq 1$. Prove that $x_{n}$ is a square for all $n$.