<s>[INST] Prove that $a_n$ is a perfect square 
  
*
  
*Let $\,\,\,\left(a_{n}\right)_{\ n\ \in\ \mathbb{N}\,\,\,}$ be the sequence of integers defined recursively by
  $$
a_{1} = a_{2} = 1\,,\qquad\quad a_{n + 2} = 7a_{n + 1} -a_{n} - 2\quad
\mbox{for}\quad n \geq 1
$$
  
*Prove that $a_{n}$ is a perfect square for every $n$.
  

We have $a_{3} = 4, a_{4} = 25, a_{5} = 169,\ldots$

Is there a way we can simplify the recursion or get its closed form in order to get that it is a perfect square ?.
 [/INST] Define the sequence given by $b_1=1,b_2=1$ and $b_{n+2}=3b_{n+1}-b_{n}$ for $n>0$.
To prove that $a_n=b_n^2$ we just have to show:
$b_{n+2}^2=7b_{n+1}^2-b_{n}^2-2$.
Of course $b_{n+2}^2=9b_{n+1}^2-6b_{n+1}b_n+b_{n-1}^2$
So to finish we just need to prove $3b_{n+1}b_n=b_{n+1}^2+b_n^2+1$.
Notice $b_{n+1}^2+b_n^2+1=b_{n+1}(3b_n-b_{n-1})+b_n^2+1=3b_{n+1}b_n-b_{n+1}b_{n-1}+b_n^2+1$.
So to finish we just have to show $b_{n+1}b_{n-1}-b_n^2=1$
To do this we notice that 
$$
\begin{pmatrix}
3 & 1\\
-1 & 0
\end{pmatrix}^n
\begin{pmatrix}
2 & 1\\
1 & 1
\end{pmatrix}
= 
\begin{pmatrix}
b_{n+3} & b_{n+2}\\
b_{n+2} & b_{n+1}
\end{pmatrix}$$
Therefore the the determinant of the matrix on the right is always $1$, and that determinant is $b_{n+3}b_{n+1}-b_{n+2}^2$
</s>