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 ?.

A brute-force approach
$$b_{n} = 3b_{n-1} - b_{n-2}$$
Squaring on both sides,
$$b_n^2 = 9b_{n-1}^2+b_{n-2}^2 -6b_{n-1}b_{n-2} $$
Similarly,
$$b_{n-1}^2 = 9b_{n-2}^2+b_{n-3}^2 -6b_{n-2}b_{n-3} $$
Subtracting,
$$b_n^2 - b_{n-1}^2 = 9b_{n-1}^2 - 8b_{n-2}^2 - b_{n-3}^2 -6a_{n-2}(b_{n-1}-b_{n-1}) $$
Since,
$$3b_{n-2} = b_{n-1} + b_{n-3}$$
$$b_n^2 - b_{n-1}^2 = 9b_{n-1}^2 - 8b_{n-2}^2 - b_{n-3}^2 -2(b_{n-1} + b_{n-3})(b_{n-1}-b_{n-3}) $$
$$b_n^2 - b_{n-1}^2 = 9b_{n-1}^2 - 8b_{n-2}^2 - b_{n-3}^2 -2(b_{n-1}^2 - b_{n-3}^2) $$
$$b_n^2 = 8(b_{n-1}^2 - b_{n-2}^2) + b_{n-3}^2 $$
Summing up both sides from 3 to n,
$$\sum_{i=3}^{n}(b_i^2-b_{i-3}^2)=8\sum_{i=3}^{n}(b_{i-1}^2 - b_{i-2}^2)$$
$$\sum_{i=3}^{n}b_i^2-\sum_{j=0}^{n-3}b_{j}^2=8(\sum_{k=2}^{n-1}b_{k}^2 - \sum_{l=1}^{n-2}b_{l}^2)$$
$$b_n^2 + b_{n-1}^2 +b_{n-2}^2 - b_{2}^2 -b_{1}^2-b_{0}^2= 8(b_{n-1}^2 - b_1^2) $$
$$b_n^2 = 7b_{n-1}^2 - b_{n-2}^2 -2 $$
$\therefore a_n=b_n^2$ satisfies the recurrence.
Hence,proved
