<s>[INST] How do you rewrite a determinant of a matrix into a polynomial by induction? 
$$\det\begin{bmatrix} {x} & {0} & {\cdots} & {\cdots} & {0} & {a_{1}} \\  {-1} & {x} & {0} & {\cdots} & {0} & {a_{2}} \\ {\ddots} & {\ddots} & {\ddots} & {\ddots} & {\vdots} & {\vdots} \\ {\cdots} & {0} & {-1} & {x} & {0} & {a_{n-3}} \\{\cdots} & {\cdots} & {0} & {-1} & {x} & {a_{n-2}} \\{\cdots} & {\cdots} & {\cdots} & {0} & {-1} & {a_{n-1}+x} \end{bmatrix}=a_1+a_2x+\cdots+a_{n-1}x^{n-2}+x^{n-1}$$

How can I replace the determinant on the left by induction to get $a_1+a_2x+\cdots+a_{n-1}x^{n-2}+x^{n-1}$? I need this to determine the determinant of the companion matrix and I don't understand how this step is done. Thanks in advance!
 [/INST] We wish to prove the following by induction:
$$
\det
\begin{pmatrix}
t & 0 & \cdots & 0 & a_0 \\
-1 &  t & \cdots & 0 & a_1 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & -1 & t+a_{n-1} \end{pmatrix}
=a_0+a_1t+\cdots+a_{n-1}t^{n-1}+t^n
$$
When $n=1$ we have that
$$
\det
\begin{pmatrix}
a_0+t
\end{pmatrix}
=a_o+t
$$
Now supposing that we've proved the claim holds for $n$, we will try to prove the claim holds for $n+1$. Starting with
$$
\det
\begin{pmatrix}
t & 0 & \cdots & 0 & a_0 \\
-1 &  t & \cdots & 0 & a_1 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & -1 & t+a_n \end{pmatrix}
$$
we do co-factor expansion on the first row we get
$$
t\cdot\det
\begin{pmatrix}
t & 0 & \cdots & 0 & a_1 \\
-1 & t & \cdots & 0 & a_2 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & -1 & t+a_n
\end{pmatrix}
+(-1)^n\cdot a_0\cdot\det
\begin{pmatrix}
-1 & t & \cdots & 0 \\
0 & -1 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & -1
\end{pmatrix}
$$
The determinant on the right is $(-1)^n$, and from our induction hypothesis, the determinant of the left is $a_1+a_2t+\cdots+a_nt^{n-1}+t^n$. Hence we have that
$$
\begin{align*}
\det
\begin{pmatrix}
t & 0 & \cdots & 0 & a_0 \\
-1 &  t & \cdots & 0 & a_1 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & -1 & t+a_n \end{pmatrix}
&= t\cdot(a_1+a_2t+\cdots+a_nt^{n-1}+t^n)+(-1)^n\cdot a_0\cdot(-1)^n\\
&= a_1t+\cdots+a_nt^n+t^{n+1}+a_o \\
&= a_0+a_1t+\cdots+a_nt^n+t^{n+1}
\end{align*}
$$
This shows the claim holds for $n+1$ assuming it held for $n$.
</s>