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$?
 A: 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 $$
A: Here's a generating function approach. Plugging the recursion into $G(x):=\sum_{n=0}^\infty z_nx^n$, obtain
$$
\begin{align}
G(x)&=z_0+z_1x+\sum_2 z_nx^n=1+x+\sum_2(7z_{n-1}-z_{n-2}-2)x^n\\&=1+x+7x[G(x)-1]-x^2G(x)-\frac{2x^2}{1-x}.
\end{align}
$$
Solve for $G(x)$:
$$
G(x)=\frac{1-7x+4x^2}{(1-x)(1-7x+x^2)}.\tag1
$$
The roots of $x^2-7x+1$ are $\frac{7\pm3\sqrt 5}2$, which we recognize as $\phi^4$ and $\phi^{-4}$, where $\phi:=\frac{\sqrt 5+1}2$. Writing $f:=\phi^4$ for brevity, decompose (1) in partial fractions:
$$
G(x)=\frac A{1-x}+\frac B{f-x}+\frac C{f^{-1}-x}=
\sum_0 \left[A+Bf^{-1}f^{-n}+Cff^n\right]x^n.\tag2
$$
Solving for $A, B, C$ we find $A=\frac25$, $Bf^{-1}=\frac{\phi^2}5$, and $Cf=\frac{\phi^{-2}}5$. Matching the coefficients of (2) with those of $G(x)=\sum_0z_nx^n$, conclude
$$
z_n=\frac25+\frac{\phi^2}5f^{-n}+\frac{\phi^{-2}}5f^n
=\frac15\left(\phi^{4n-2}+2+\phi^{-(4n-2)}\right)=\left[\frac{\phi^{2n-1}+\phi^{-(2n-1)}}{\sqrt 5}\right]^2,
$$
and the quantity in square brackets is the $(2n-1)$th Fibonacci number.
