Recursive relation for a characteristic polynomial I need to find a recursive relation for the characteristic polynomial of the $k \times k $ matrix $$\begin{pmatrix} 0 &amp; 1 \\ 1 &amp; 0 &amp; 1 \\ \mbox{ } &amp;  1 &amp; . &amp; . \\ \mbox{ } &amp;\mbox{ } &amp; . &amp; . &amp;. &amp; \mbox{ } \\ \mbox{ } &amp;\mbox{ } &amp;\mbox{ } &amp; . &amp; . &amp; 1 \\ \mbox{ } &amp; \mbox{ } &amp; \mbox{ } &amp; \mbox{ } &amp; 1 &amp; 0\end{pmatrix}$$

I calculate the $3 \times 3$ and $4 \times 4$ case but I couldn't deduce a recursive formula.
The characteristic polynomial of your matrix (say, $A$) is the determinant of the tridiagonal Toeplitz matrix $xI-A$. So, as long as you know how to evaluate the determinant of a tridiagonal matrix recursively (see this question and its answers for examples), you can deduce a recursive formula.
The characteristic polynomial of your matrix (say, $A$) is the determinant of the tridiagonal Toeplitz matrix $xI-A$. So, as long as you know how to evaluate the determinant of a tridiagonal matrix recursively (see this question and its answers for examples), you can deduce a recursive formula.