How to compute the determinant of this Toeplitz matrix? 
Given a positive integer $n$, express$$
f_n(x) = \left|\begin{array}{c c c c c} 
1 & x & \cdots & x^{n - 1} & x^n\\
x & 1 & x & \cdots & x^{n - 1} \\
\vdots & x & \ddots & \ddots & \vdots\\
x^{n - 1} & \vdots & \ddots & 1 & x\\
x^n & x^{n - 1} & \cdots & x & 1
\end{array}\right|
$$
  as a polynomial of $x$.

I tried to find a recurrence relation of $\{f_n\}_{n \geqslant 1}$ using Laplace expansion, but there seems to be no patterns in the minors in the expansion. Is there a somewhat simple recurrence relation of $\{f_n\}_{n \geqslant 1}$ or these determinants can be computed with other methods?
 A: @José Carlos Santos I cannot compete with your straightforward proof.
Nevertheless, I thought it could be interesting to provide a (longer...) proof by using a rather peculiar property of the given matrix : the fact that its inverse is the following tridiagonal $(n+1) \times (n+1)$ matrix :
$$\dfrac{1}{1-x^2}T_n \ \ \ \ \text{where} \ \ \ \ T_n:=\begin{pmatrix} 
1&      -x&    0  & \cdots&       0&  0\\
-x& x^2 + 1&  -x &    \ddots&       0&       0\\
0&  -x& x^2 + 1&      \ddots& 0 &0\\
 0&0&  -x& \ddots&      -x &0\\
 0&0&  \ddots& \ddots&     x^2+1 &-x\\
  0&0&\cdots&  0&       -x&1\end{pmatrix}$$
with exceptional entries $1$ in $(1,1)$ and $(n+1,n+1)$.
Let $S_n$ be the initial matrix ; it is indeed easy to verify that $S_n T_n=(1-x^2)I_{n+1}$.
Let us prove now that, whatever $n$, the determinant of $T_n$ has the constant expression:
$$\tag{1}\det(T_n)=(1-x^2).$$
Let us multiply the first line of $\det(T_n)$ by $x$, then add this new line to the second line (this operation doesn't modify $\det(T_n)$). Laplace expansion along the first column gives:
$$x\det(T_n)=x\det(T_{n-1}).$$
Knowing that $\det(T_1)=1-x^2$ by direct computation, we have reached our objective (1).
As a consequence,
$$\det(S_n)=\left(\dfrac{1}{(1-x^2)^{n+1}}\det(T_n)\right)^{-1}=(1-x^2)^n.$$
Remark : There is a nice interpretation of the initial matrix $S_n$ as the covariance matrix of an autoregressive process $V_{n+1}=xV_n+aX$ with $X \sim N(0,1)$ (see for the continuous case (https://www.le.ac.uk/users/dsgp1/COURSES/ELOMET/LECTURE5.PDF)). The inverse of a covariance matrix is almost as significant as the initial covariance matrix. See (https://stats.stackexchange.com/q/73463) for its different uses/interpretations.
A: Let matrix-valued function $\mathrm M_1 : \mathbb R \to  \mathbb R^{2 \times 2}$ be defined as follows
$$\mathrm M_1 (x) := \begin{bmatrix} 1 & x\\ x & 1\end{bmatrix}$$
and let matrix-valued function $\mathrm M_n : \mathbb R \to  \mathbb R^{(n+1) \times (n+1)}$ be defined by
$$\mathrm M_n (x) := \begin{bmatrix} \mathrm M_{n-1} (x) &  \mathrm v_{n} (x)\\ \mathrm v_{n}^\top (x) & 1\end{bmatrix}$$
where $\mathrm v_{n}^\top (x) := \begin{bmatrix} x^n & \cdots & x^2 & x\end{bmatrix}$. Let function $f_n : \mathbb R \to  \mathbb R$ be defined by
$$f_n (x) := \det \mathrm M_n (x) = \det \begin{bmatrix} \mathrm M_{n-1} (x) &  \mathrm v_{n} (x)\\ \mathrm v_{n}^\top (x) & 1\end{bmatrix} = \det \left( \mathrm M_{n-1} (x) - \mathrm v_{n} (x) \, \mathrm v_{n}^\top (x) \right)$$
Using the matrix determinant lemma,
$$f_n (x) = \underbrace{\det \left( \mathrm M_{n-1} (x) \right)}_{= f_{n-1} (x)} \cdot  \left( 1 - \mathrm v_{n}^\top (x) \, \mathrm M_{n-1}^{-1} (x) \, \mathrm v_{n} (x) \right)$$
Let $\mathrm y (x) := \mathrm M_{n-1}^{-1} (x) \, \mathrm v_{n} (x)$ be the solution of the linear system $\mathrm M_{n-1} (x) \,\mathrm y (x) = \mathrm v_{n} (x)$. Since $\mathrm v_{n} (x)$ is equal to the $n$-th column of $\mathrm M_{n-1} (x)$ multiplied by $x$, the solution is $\mathrm y (x) = x \, \mathrm e_n$. Thus,
$$f_n (x) = f_{n-1} (x) \cdot \left( 1 - \mathrm v_{n}^\top (x) \, \mathrm y (x) \right) = f_{n-1} (x) \cdot \left( 1 - x^2 \right)$$
Since $f_1 (x) = 1 - x^2$, we obtain $\color{blue}{f_n (x) = (1-x^2)^n}$, as found by José Carlos Santos via other means.
A: The answer is: $f_n(x)=(1-x^2)^n$.
You can prove that this is true by induction. If you subtract from the first row the second row times $x$, all the entries of the first line after the first one become $0$ (and the first one is $1-x^2$). Therefore, $f_n(x)=(1-x^2)f_{n-1}(x)$. Since $f_1(x)=1-x^2$, you're done.
A: Subtract $x$ times row $2$ from row $1$, then $x$ times row $3$ from row $2$ etc. I get a lower triangular matrix with $n$ instances of $1-x^2$ on the diagonal and one $1$.
A: This is simply an illustration of José Carlos Santos' answer.

Subtracting $x$ times the second column from the first gives
$$
\begin{align}
f_n(x)
&=\det\begin{bmatrix}
1&x&x^2&x^3&\cdots&x^n\\
x&1&x&x^2&\cdots&x^{n-1}\\
x^2&x&1&x&\cdots&x^{n-2}\\
x^3&x^2&x&1&\cdots&x^{n-3}\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\
x^n&x^{n-1}&x^{n-2}&x^{n-3}&\cdots&1
\end{bmatrix}\\
&=\det\begin{bmatrix}
\color{#C00}{1-x^2}&x&x^2&x^3&\cdots&x^n\\
0&\color{#090}{1}&\color{#090}{x}&\color{#090}{x^2}&\color{#090}{\cdots}&\color{#090}{x^{n-1}}\\
0&\color{#090}{x}&\color{#090}{1}&\color{#090}{x}&\color{#090}{\cdots}&\color{#090}{x^{n-2}}\\
0&\color{#090}{x^2}&\color{#090}{x}&\color{#090}{1}&\color{#090}{\cdots}&\color{#090}{x^{n-3}}\\
\vdots&\color{#090}{\vdots}&\color{#090}{\vdots}&\color{#090}{\vdots}&\color{#090}{\ddots}&\color{#090}{\vdots}\\
0&\color{#090}{x^{n-1}}&\color{#090}{x^{n-2}}&\color{#090}{x^{n-3}}&\color{#090}{\cdots}&\color{#090}{1}
\end{bmatrix}\\[6pt]
&=\color{#C00}{\left(1-x^2\right)}\color{#090}{f_{n-1}(x)}
\end{align}
$$
Since $f_0(x)=1$, we have that
$$
f_n(x)=\left(1-x^2\right)^n
$$
