Matrix determinant as Dickson polynomial $\frac{x^{n+1}-y^{n+1}}{x-y}$ 
Given matrix $$
A=\begin{bmatrix}
x+y&xy&0& .&.&. &0\\
1&x+y&xy&0& .&.&0 \\
0&1&x+y&xy&.&.&. \\
.&.&.&.&.&.&. \\
.&.&.&.&.&.&0 \\
.&.&.&.&.&.&xy \\
0&.&.&.&0&1&x+y
\end{bmatrix}
$$
prove by induction that $$|A|=\frac{x^{n+1}-y^{n+1}}{x-y}$$ $x \neq y$, $A_{n \times n}$.

The determinant expression appears to be Dickson polynomial of second kind.
Let $D_n$ be the determinant of $A_n$. We can see that the appropriate recurrence relation is $$D_n=(x+y)D_{n-1}-xyD_{n-2}$$
Base cases:
$$D_1=x+y=\frac{x^2-y^2}{x-y}$$
$$
D_2=(x+y)^2-xy=x^2+xy+y^2=\frac{x^3-y^3}{x-y}
$$
Suppose that $$D_n=(x+y)D_{n-1}-xyD_{n-2}$$
Then we need to prove that $$D_{n+1}=(x+y)D_{n}-xyD_{n-1}$$
Which can be developed as:
$$
D_{n+1}=(x+y)((x+y)D_{n-1}-xyD_{n-2})-xyD_{n-1}=
$$
$$
=(x+y)^2D_{n-1}-xy(x+y)D_{n-2}-xyD_{n-1}=
$$
$$
=(x^2+xy+y^2)D_{n-1}-xy(x+y)D_{n-2}=
$$
$$
=\frac{x^3-y^3}{x-y}D_{n-1}-xy(x+y)D_{n-2}
$$
I tried doing this up to $D_{n-6}$ in order to get any insights into possible simplification but I'm pretty stuck.
 A: A linear algebra approach to the recurrence relation is to write it in matrix form: $$\mathcal{D}_n\equiv \begin{pmatrix} D_{n} \\ D_{n-1}\end{pmatrix}=\begin{pmatrix} x+y & -xy\\1 & 0 \end{pmatrix}\begin{pmatrix} D_{n-1} \\ D_{n-2}\end{pmatrix}\equiv M \mathcal{D}_{n-1},\hspace{4mm} \mathcal{D}_0 = \binom{1}{0}.$$ (I choose $D_0=1,D_{-1}=0$ so that the recurrence for $D_n$ in terms of $D_{n-1},D_{n-2}$ valid for $n\geq 1$.) Then $D_n=(\mathcal{D}_n)_1=(M^n \mathcal{D}_0)_1=(M^n)_{11},$ so computing $D_n$ amounts to matrix multiplication. But the eigenvalues and eigenvectors are simple enough in this case, yielding the spectral decomposition $$M=\Lambda D \Lambda^{-1}=\begin{pmatrix}x & y \\ 1 & 1\end{pmatrix}\begin{pmatrix}x & 0 \\ 0 & y\end{pmatrix}\begin{pmatrix}x & y \\ 1 & 1\end{pmatrix}^{-1}$$
and therefore 
\begin{align}
M^n 
&=(\Lambda D \Lambda^{-1})^n \\
&= \Lambda D^n \Lambda^{-1} \\
&= \begin{pmatrix}x & y \\ 1 & 1\end{pmatrix}\begin{pmatrix}x^n & 0 \\ 0 & y^n\end{pmatrix}\begin{pmatrix}x & y \\ 1 & 1\end{pmatrix}^{-1} \\
&= \begin{pmatrix}x^{n+1} & y^{n+1} \\ x^n & y^n\end{pmatrix}\cdot \frac{1}{x-y}\begin{pmatrix}1 & -y \\ -1 & x\end{pmatrix}\\
&=\frac{1}{x-y}\begin{pmatrix}x^{n+1}-y^{n+1} & x y^{n+1}-x^{n+1}y \\ x^{n}-y^{n}& xy^{n}-yx^{n}\end{pmatrix}.
\end{align}
From the upper-left corner we read off the anticipated result.
A: Your base cases are good. For the induction step, assume that
$$D_n=\frac{x^{n+1}-y^{n+1}}{x-y}\quad \text{and}\quad D_{n-1}=\frac{x^{n}-y^{n}}{x-y}.$$
Then you have that
$$D_{n+1}=(x+y)D_n-xyD_{n-1},$$so you only have to show that
$$(x+y)\frac{x^{n+1}-y^{n+1}}{x-y}-xy\frac{x^{n}-y^{n}}{x-y}=\frac{x^{n+2}-y^{n+2}}{x-y}.$$
Developping the LHS gives you
\begin{align}(x+y)\frac{x^{n+1}-y^{n+1}}{x-y}-xy\frac{x^{n}-y^{n}}{x-y} & = \frac{x^{n+2}+x^{n+1}y-xy^{n+1}-y^{n+2}-x^{n+1}y+xy^{n+1}}{x-y}\\ & = \frac{x^{n+2}-y^{n+2}}{x-y}.\end{align}
A: You did the base cases $n=1,2$, then you do the inductive step using strong induction; suppose your claim is true for any $m \leq n$, then using the recursive formula, for $n \geq 3$:
\begin{align}
D_{n+1} &=(x+y)D_n-xyD_{n-1} =\\ 
&=(x+y)\frac{x^{n+1}-y^{n+1}}{x-y} -xy\frac{x^n-y^n}{x-y} = \\
&= \frac{1}{x-y}(x^{n+2}-xy^{n+1}+yx^{n+1}-y^{n+2}-x^{n+1}y+xy^{n+1})= \\
&= \frac{x^{n+2}-y^{n+2}}{x-y}
\end{align}
which proves the claim for $m=n+1$. By induction, the claim is true for any $n$.
