Characteristic polynomials for a class of simple matrices Let $M_{k}$ be the kxk-matrix  with entries  $m(i,j,k)=0$  for $i+j<k-1$ and $m(i,j,k)=1$ else.
For example $M_{3}=\begin{bmatrix}0 & 0 & 1\\0&1&1\\ 1&1&1\end{bmatrix}.$
Let $F_{n}(x)$ denote the Fibonacci polynomials defined by $F_{n}(x)= F_{n-1}(x)+x F_{n-2}(x)$ with initial values $ F_{0}(x)= F_{1}(x)=1.$
Computations suggest that the characteristic polynomial  of $M_{k}^2$ is $F_{2k}(-x)=\sum_{j=0}^k\binom{2k-j}{j}(-x)^k.$
Is there a simple proof of this result?
 A: The squares $N_k = M_k^2$ are very nice matrices: we have (indexing from $1$ to $k$)
$$N_k(i, j) = \text{min}(i, j)$$
hence, for example,
$$N_4 = \left[ \begin{array}{cc} 1 & 1 & 1 & 1 \\ 1 & 2 & 2 & 2 \\ 1 & 2 & 3 & 3 \\ 1 & 2 & 3 & 4 \end{array} \right].$$
Define the polynomials $P_k(x) = \det (N_k - xI)$, and (it turns out we will need this) also define $Q_k(x)$ to be the determinant of $N_k - \text{diag}(x, x, \dots 0)$. Subtracting the second-to-last-row from the last row of $N_k - xI$ gives last row $(0, 0, \dots x, 1-x)$, and Laplace expanding along this row gives
$$P_k(x) = (1 - x) P_{k-1}(x) - x Q_{k-1}(x).$$
The same row operation for $N_k - \text{diag}(x, x, \dots 0)$ gives last row $(0, 0, \dots x, 1)$, and Laplace expanding along this row gives
$$Q_k(x) = P_{k-1}(x) - x Q_{k-1}(x).$$
This gives
$$\left[ \begin{array}{c} P_k(x) \\ Q_k(x) \end{array} \right] = \left[ \begin{array}{cc} 1-x & -x \\ 1 & -x \end{array} \right] \left[ \begin{array}{c} P_{k-1}(x) \\ Q_{k-1}(x) \end{array} \right]$$
which, together with the initial conditions $P_0(x) = 1, Q_0(x) = 0$ (which you can check is consistent with $P_1(x) = 1-x, Q_1(x) = 1$), gives
$$\left[ \begin{array}{c} P_k(x) \\ Q_k(x) \end{array} \right] = \left[ \begin{array}{cc} 1-x & -x \\ 1 & -x \end{array} \right]^n \left[ \begin{array}{cc} 1 \\ 0 \end{array} \right].$$
So $P_k(x)$ satisfies a linear recurrence relation with characteristic polynomial the characteristic polynomial of $\left[ \begin{array}{cc} 1-x & -x \\ 1 & -x \end{array} \right]$, which is
$$\lambda^2 - (1-2x) \lambda + x^2.$$
This gives $P_0(x) = 1, P_1(x) = 1 - x$, and
$$P_k(x) = (1 - 2x) P_{k-1}(x) - x^2 P_{k-2}(x).$$
This matches up to your Fibonacci polynomials by induction, although note that Wikipedia uses different initial conditions and puts the $x$ in a different place than you and I don't know which convention is standard. To see this concretely write
$$F_{2k}(-x) = F_{2k-1}(-x) - x F_{2k-2}(-x)$$
$$F_{2k-1}(-x) = F_{2k-2}(-x) - x F_{2k-3}(-x)$$
$$F_{2k-2}(-x) = F_{2k-3}(-x) - x F_{2k-4}(-x)$$
Writing the third equation as $F_{2k-3}(-x) = F_{2k-2}(-x) + x F_{2k-4}(x)$ and substituting twice to remove the odd terms gives
$$F_{2k}(-x) = (1 - 2x) F_{2k-2}(-x) - x^2 F_{2k-4}(-x)$$
as desired.
More abstractly, $F_k(-x)$ satisfies a recurrence relation with characteristic polynomial $\lambda^2 - \lambda + x$ so it can be expressed as a sum of $k^{th}$ powers of the two roots of this polynomial. This means $F_{2k}(-x)$ satisfies a recurrence relation with characteristic polynomial the polynomial whose roots are the squares of $\lambda^2 - \lambda + x$. In general, if $\lambda^2 - b \lambda + c$ has roots $r, s$, the polynomial with roots $r^2, s^2$ is $\lambda^2 - (b^2 - 2c) \lambda + c^2$ and applying this transformation to $\lambda^2 - \lambda + x$ gives $\lambda^2 - (1 - 2x) \lambda + x^2$ as expected.
