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: 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$
A: Cleaned Up for Clarity:
Recall the Fibonacci sequence:
$$1, 1, 2, 3, 5, 8, 13, \ldots$$
You have here the sequence:
$$1^2, 2^2, 5^2, 13^2, \ldots$$
So: It looks to be the odd entries of the Fibonacci sequence, squared.
To check if this holds, we proceed as follows:
Note $F(2k-1)^2$ and $a(k)$ have the same first two values; so we can verify whether they produce the same sequences by checking if $F(2k-1)^2$ satisfies the same recurrence relation as $a(k)$.
Short Answer: The relation holds for $F(2k-1)^2$ as can be shown by appealing directly to the closed formula for the Fibonacci entries. QED.

Longer Answer: To check that the relation holds, we first recall the recursive $a(k)$ definition:
$$a(k+2) = 7a(k+1) - a(k) - 2$$
To prove that $F(2k-1)^2$ satisfies this relation, we check if the following holds:
$$F(\text{the }k+2\text{nd odd})^2 = 7F(\text{the }k+1\text{st odd})^2 - F(\text{the }k\text{th odd})^2 - 2$$
Note: The $(k+2)$nd odd is $2k+3$; the $(k+1)$st odd is $2k+1$; the $k$th odd is $2k-1$.
Since we have an explicit formula for the $n$th entry in the Fibonacci sequence, we can use it to check whether the recurrence relation above holds. To check that it holds, it suffices to subtract the LHS from the RHS and see if it returns $0$; this is done in the Wolfram Alpha link here. 
The result is given as $-4 \sin^2 (\pi n)$, which is not the cleanest method of verification; but observe that any natural multiple of $\pi$ is zero when evaluated at $\sin$. So the result follows. QED.
A: For first, we may translate our sequence in order to have some sequence fulfilling $b_{n+2}=7b_{n+1}-b_n$. For such a purpose, it is enough to set $a_n=b_{n}+\frac{2}{5}$, leading to $b_0=b_1=\frac{3}{5}$. Now the characteristic polynomial of the sequence $\{b_n\}_{n\geq 0}$ is
$$ p(x)=x^2-7x+1 $$
with roots given by $\frac{7\pm 3\sqrt{5}}{2}$, so the explicit form of $b_n$ is given by:
$$ b_n = A\left(\frac{7+3\sqrt{5}}{2}\right)^2+B\left(\frac{7-3\sqrt{5}}{2}\right)^n $$
where the values of the constants $A,B$ are fixed by $b_0$ and $b_1$:
$$ b_n = \frac{-\sqrt{5}+3}{10}\left(\frac{7+3\sqrt{5}}{2}\right)^2+\frac{\sqrt{5}+3}{10}\left(\frac{7-3\sqrt{5}}{2}\right)^n. $$
Now the identity:
$$\boxed{ a_n = b_n+\frac{2}{5} = F_{2n-1}^2 }$$
is a simple consequence of the closed formula for Fibonacci numbers.
A: 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
