How to proof $f_{n+1}(x) = x f_n(x) - f_{n-1} (x),\quad n \geqslant 1$ by induction?

Question

Let $$ f_n (x) = \det \begin{bmatrix} x & 1 & 0 & \cdots & 0 \\ 1 & x & 1 & 0 & 0 \\ 0 & 1 & x & 1 & \vdots \\ \vdots & & & \ddots & 1 \\ 0 & \cdots & & 1 & x \end{bmatrix},$$ with the matrix of order $n$. Also define $f_0 (x) \equiv 1$.

How to show this recursive formula by induction? Is there any other way to prove it?: $$f_{n+1}(x) = x f_n(x) - f_{n-1} (x),\quad n \geqslant 1$$

Answer 1

Starting with the $(n+1)\times (n+1)$ matrix in computing $f_{n+1}(x)$, expand along the first row to get $f_{n+1} = xf_n(x) - f_{n-1}(x)$.

Answer 2

Tip: This is easily done using the Laplace expansion : http://en.wikipedia.org/wiki/Laplace_expansion