<s>[INST] Inverse of tridiagonal Toeplitz matrix Consider  the following tridiagonal Toeplitz matrix. Let $n$ be even.
$${A_{n \times n}} = \left[ {\begin{array}{*{20}{c}}
{0}&{1}&{}&{}&{}\\
{1}&{0}&{1}&{}&{}\\
{}&{1}&{\ddots}&{\ddots}&{}\\
{}&{}&{\ddots}&{\ddots}&{1}\\
{}&{}&{}&{1}&{0}
\end{array}} \right]$$
What is the inverse $A^{-1}$? 
Clearly, $A^{-1}$ is symmetric.
I look for a proof of the following conjecture that $A^{-1}$ is given as follows:
If $A_{i, j}^{-1}$ such that $j$ is odd and $i =1+j + 2 m$ with $m\in \cal N_0$, then $A_{i, j}^{-1} = (-1)^m$. From which follows by symmetry:
If $A_{i, j}^{-1}$ such that $j$ is even and $i =-1+j - 2 m$ with $m\in \cal N_0$, then $A_{i, j}^{-1} = (-1)^m$. 
All other $A_{i, j}^{-1} = 0$.
Here is an example, computed with Matlab, for $n=10$ which shows the structure: 
$${A_{10 \times 10}^{-1}} = \left[ {\begin{array}{*{20}{r}}
0 &     1 &     0 &    -1 &      0 &     1 &     0 &    -1 &      0 &     1 \\
     1 &     0 &     0 &     0 &     0 &     0 &     0 &     0 &     0 &     0 \\
     0 &     0 &     0 &     1 &     0 &    -1 &     0 &     1 &     0 &    -1  \\
    -1 &      0 &     1 &     0 &     0 &     0 &     0 &     0 &     0 &     0 \\
     0 &     0 &     0 &     0 &     0 &     1 &     0 &    -1 &      0 &     1 \\
     1 &     0 &    -1 &     0 &     1 &     0 &     0 &     0 &     0 &     0 \\
     0 &     0 &     0 &     0 &     0 &     0 &     0 &     1 &     0 &    -1  \\
    -1 &     0 &     1 &     0 &    -1 &     0 &     1 &     0 &     0 &     0 \\
     0 &     0 &     0 &     0 &     0 &     0 &     0 &     0 &     0 &     1 \\
     1 &     0 &    -1 &     0 &     1 &     0 &    -1 &     0 &     1 &     0 
\end{array}} \right]$$
 [/INST] I found an algorithm that I hope it help you. Let the inverse be$$A^{-1}=\begin{bmatrix}c_1&c_2&\cdots&c_n\end{bmatrix}$$In other words, $c_i$s are the columns of $A^{-1}$. We build the $c_i$s recursively as following:
$$c_{2}=e_1\\c_{2k+2}=-c_{2k}+e_{2k+1}\qquad,\qquad 1\le k\le {n\over 2}-1$$also $$c_{n-1}=e_n\\c_{2k-1}=e_{2k}-c_{2k+1}\qquad,\qquad 1\le k\le {n\over 2}-1$$where $e_i$s are the columns of $I_n$ 
</s>