Berkeley Math Circle: Monthly Contest 2

Solution:
We claim that $a_{n} = F_{2n-1}^{2}$, where $F_{n}$ is the $n$$\text{th}$ Fibonacci number. For the base case, we compute the first four values:
$$\begin{gathered} a_{1} = 1^{2} = F_{1}^{2}, \quad a_{2} = 7 \cdot 1 - 1 - 2 = 2^{2} = F_{3}^{2} \\ a_{3} = 7 \cdot 4 - 1 - 2 = 5^{2} = F_{5}^{2}, \quad a_{4} = 7 \cdot 25 - 4 - 2 = 13^{2} = F_{7}^{2} . \end{gathered}$$
Now assume the statement holds for all $1 \leq k \leq n$ for $n \geq 4$. For the inductive step, we subtract $a_{n} = 7 a_{n-1} - a_{n-2} - 2$ from $a_{n+1} = 7 a_{n} - a_{n-1} - 2$ to get
$$a_{n+1} = 8 a_{n} - 8 a_{n-1} + a_{n-2} = 8 F_{2n-1}^{2} - 8 F_{2n-3}^{2} + F_{2n-5}^{2} .$$
But we find that for any $m \geq 2$,
$$\begin{gathered} F_{m-2} = F_{m} - F_{m-1} = F_{m} - \left(F_{m+1} - F_{m}\right) \\ \quad = 2 F_{m} - \left(F_{m+2} - F_{m}\right) = 3 F_{m} - F_{m+2} \end{gathered}$$
Substituting this in first with $m = 2n-3$ and then $m = 2n-1$ gives
$$\begin{aligned} a_{n+1} = & 8 F_{2n-3}^{2} - 8 F_{2n-1}^{2} + \left(3 F_{2n-3} - F_{2n-1}\right)^{2} \\ & = \left(3 F_{2n-1} - F_{2n-3}\right)^{2} = F_{2n+1}^{2} \end{aligned}$$
which completes the induction.