Show that $z_n$ is a perfect square if $z_0 = z_1 = 1$ and $z_{n+1} = 7z_n − z_{n−1} − 2$ Let $z_0 = z_1 = 1$ and $$z_{n+1} = 7z_n − z_{n−1} − 2$$ for all positive integers $n$. How is it possible to show that $z_n$ is a perfect square for all $n$?

I answered the last one this way, let me make it easier reading
LEMMA if $$w_{n+3} - (M+1)w_{n+2} + (M+1)w_{n+1} - w_n = 0,$$ then $w_{n+2} - M w_{n+1} + w_n$ is CONSTANT
PROOF:  $$ (w_{n+3} - M w_{n+2} + w_{n+1}) - w_{n+2} + M w_{n+1} - w_n = 0 \; ,   $$
$$w_{n+3} - M w_{n+2} + w_{n+1} = w_{n+2} - M w_{n+1} + w_{n} $$
This is constant for all $n$ by induction.
Let $(x_n,y_n)$ begin with $(1,0),$ $(1,1),$ $(2,3)$ be solutions to $x^2 + xy-y^2 = 1,$ with the rule for getting to the next solution is
$$
\left(
\begin{array}{cc}
1&1\\
1&2
\end{array}
\right)
\left(
\begin{array}{c}
x_n\\
y_n
\end{array}
\right) =
\left(
\begin{array}{c}
x_{n+1}\\
y_{n+1}
\end{array}
\right)
$$
It is easy to check that if $(a,b)$ satisfies $x^2 + xy-y^2 = 1,$ so does $(a+b,a+2b).$
It follows from Cayley-Hamilton that $x_n$ satisfies
$$  x_{n+2} - 3 x_{n+1} + x_n = 0. $$
 Analogous for $y_n.$
Next, from Fricke and Klein (1897) or direct calculation,
$$
\left(
\begin{array}{ccc}
1&2&1\\
1&3&2 \\
1&4&4
\end{array}
\right)
\left(
\begin{array}{c}
x_n^2\\
x_n y_n \\
y_n^2
\end{array}
\right) =
\left(
\begin{array}{c}
x_{n+1}^2\\
x_{n+1 } y_{n+1} \\
y_{n+1}^2
\end{array}
\right)
$$
The characteristic polynomial of the three by three matrix is
$$  \lambda^3 - 8 \lambda^2 + 8 \lambda - 1   $$
Again by Cayley-Hamilton, we get
$$ x_{n+3}^2 - 8 x_{n+2}^2 + 8 x_{n+1}^2 - x_n^2 = 0  $$
From the lemma at the beginning,
$$   x_{n+2}^2 -7 x_{n+1}^2 + x_n^2  $$
is constant. Since $4 - 7 \cdot 1 + 1 = 5-7 = -2,$ we have
$$   x_{n+2}^2 -7 x_{n+1}^2 + x_n^2 = -2 $$
$$   x_{n+2}^2 =7 x_{n+1}^2 - x_n^2  -2 $$
