Determinant of a symmetric Toeplitz matrix Let $A_n = (a_{ij})$ be an $n\times n$ matrix such that $a_{ii} = 0, a_{ij} = 2$ when $|j − i| = 1$, and $a_{ij} = 1$ otherwise. The question is to find the determinant in terms of $n$. I computed the first six terms, depending on $n$, but, unfortunately, no clear relationship was found. Here they are:
\begin{align}
\det A_1&=0,\\
\det A_2&=-4,\\
\det A_3&=8,\\
\det A_4&=-7,\\
\det A_5&=0,\\
\det A_6&=7.
\end{align}
Laplace expansion turned out to be useful only if $n$ is known. How can one derive a formula for $\det A_n$ in terms of $n$?
 A: Its probably the best one can do, is to write a recursion relation 
$$
n^2 \det (n)+\left(2 n^2+3 n+2\right) \det (n-2)+\left(2 n^2+n+1\right) \det (n-1)+(n+1)^2
   \det (n-3)=0
$$
A: Here is a partial answer. Call your matrix $A_n$. We claim that
$$
\det A_n=
\begin{cases}
1-n &\text{ if }\ n\equiv1\mod 6,\\
-4 &\text{ if }\ n\equiv2\mod 6,\\
n+5 &\text{ if }\ n\equiv3\mod 6,\\
-(n+3) &\text{ if }\ n\equiv4\mod 6,\\
0 &\text{ if }\ n\equiv5\mod 6,\\
n+1 &\text{ if }\ n\equiv0\mod 6.
\end{cases}
$$
Proof. We shall prove this claim below when the remainder of $n$ divided by $6$ is not $2$.
When the remainder is $5$, $\det A_n=0$ because
$$
(1,1,0,-1,-1,\underbrace{0,1,1,0,-1,-1}_{\text{repeat}},\ldots)^T\in\ker A_n.
$$
When the remainder is $1,3,4,6$, write $A_n=B_n+ee^T$, where $e$ is the all-one vector and $B_n$ is the symmetric tridiagonal Toeplitz matrix whose main diagonal entries are $-1$s and whose super/sub-diagonal entries are ones. By Laplace expansion, it is easy to see that $\det B_n=-\det B_{n-1}-\det B_{n-2}$. Solving the recurrence relation with the initial conditions $\det B_1=-1$ and $\det B_2=0$, we get
$$
\det B_n=\begin{cases}-1\\ 0\\ 1\end{cases} \text{ when } n\equiv\begin{cases}1\\ 2\\ 3\end{cases}\mod3.\tag{1}
$$
It is straightforward to verify that
$$
B_n^{-1}e=
\begin{cases}
(-1,\underbrace{0,2,3,2,0,-1}_{\text{repeat}},\ldots)^T &\text{ if }\ n\equiv1\mod 6,\\
(2,3,2,\underbrace{0,-1,0,2,3,2}_{\text{repeat}},\ldots)^T &\text{ if }\ n\equiv3\mod 6,\\
(1,2,2,1,\underbrace{0,0,1,2,2,1}_{\text{repeat}},\ldots)^T &\text{ if }\ n\equiv4\mod 6,\\
(\underbrace{0,1,2,2,1,0}_{\text{repeat}},\ldots)^T &\text{ if }\ n\equiv0\mod 6.
\end{cases}
$$
It follows that
$$
e^TB_n^{-1}e=
\begin{cases}
n-2 &\text{ if }\ n\equiv1\mod 6,\\
n+4 &\text{ if }\ n\equiv3\mod 6,\\
n+2 &\text{ if }\ n\equiv4\mod 6,\\
n &\text{ if }\ n\equiv0\mod 6.
\end{cases}\tag{2}
$$
Hence the assertion follows from $(1), (2)$ and Sherman-Morrison formula
$$
\det A_n = \det(B_n + ee^T) = (1+e^TB_n^{-1}e) \det B_n.
$$
This completes our proof when the remainder of $n$ divided by $6$ is not $2$. When the remainder is $2$, by using the fact that $\ker A_{6k+5}\cap \ker B_{6k+5}$ is nonempty, we can actually prove that $\det A_n=-4$ by showing that the Schur complement of $A_2$ in $A_n$ has determinant $1$. However, this will make the proof too long and so we shall omit this part here.
