Computation of Determinant for Eigenvalues of Adjacency Matrix of Permutation Problem Let $P$ be a path with the vertex set $[n]$ and the edges $\{i,i-1\}$ for $1\le i\le n-1$. 
Find all eigenvalues of adjacency matrix of P.

Solution The graph given representend as follow:
$$1-2-3-4-5-6-\cdot\cdot\cdot - n-1-n$$
And its adjacency matrix $A$ computed as:
$$A =\begin{bmatrix}0&1&0&0&...&0\\1&0&1&0&...&0\\0&1&0&1&...&0\\...\\0&...&0&1&0&1&\\0&...&0&0&1&0\end{bmatrix}$$
Now, with this matrix A, to compute eigenvalues:
$$det(A-\lambda I) = 0$$
Then 
$$A-\lambda I  =\begin{bmatrix}-\lambda &1&0&0&...&0\\1&-\lambda&1&0&...&0\\0&1&-\lambda&1&...&0\\...\\0&...&0&1&-\lambda&1&\\0&...&0&0&1&-\lambda\end{bmatrix}$$

Question: How can I compute the $det(A-\lambda I)$ easily?
 A: Here's a rather different approach using cofactor expansion and induction. 

One can compute the determinants $S_n = \det(A-\lambda I_n)$ recursively, using the following method (I'll demonstrate the first few, and you'll see the pattern):
$S_1 = -\lambda$
$S_2 = \det(A-\lambda I_2) = \det\left(\begin{array}{cc}
-\lambda & 1\\
1 & -\lambda
\end{array}\right) = \lambda^2-1$
\begin{align}\begin{aligned}
S_3 &= \det(A-\lambda I_3) = \det\left(\begin{array}{ccc}
-\lambda & 1 & 0\\
1 & -\lambda & 1\\
0 & 1 & -\lambda
\end{array}\right)\\ &= -\lambda\det\left(\begin{array}{ccc}
-\lambda & 1\\
1 & -\lambda
\end{array}\right) - \det\left(\begin{array}{ccc}
1 & 1\\
0 & -\lambda\\
\end{array}\right) \quad\text{ (cofactor expand along first row)}\\&= -\lambda S_2 - S_1 \quad \text{ (cofactor expand second term along first column)}
\end{aligned}\end{align}
\begin{align}\begin{aligned}
S_4 &= \det(A-\lambda I_4)  = \det\left(\begin{array}{cccccc}
-\lambda & 1 & 0 & 0 \\
1 & -\lambda & 1 & 0 \\
0 & 1 & -\lambda & 1\\
0 & 0 & 1 & -\lambda
\end{array}\right)\\
&= -\lambda \det\left(\begin{array}{cccccc}
-\lambda & 1 & 0 \\
1 & -\lambda & 1  \\
0 & 1 & -\lambda 
\end{array}\right) - \det\left(\begin{array}{cccccc}
1 & 1 & 0 \\
0 & -\lambda & 1 \\
0 & 1 & -\lambda
\end{array}\right) \quad\text{ (cofactor expand along first row)}\\
&= -\lambda S_3 - \det\left(\begin{array}{cccccc}
-\lambda & 1 \\
1 & -\lambda
\end{array}\right) \quad \text{ (cofactor expand second term along first column)}\\
&= -\lambda S_3 - S_2
\end{aligned}\end{align}
\begin{align}\begin{aligned}
S_5 &= \det(A-\lambda I_5)  = \det\left(\begin{array}{cccccc}
-\lambda & 1 & 0 & 0 & 0\\
1 & -\lambda & 1 & 0 & 0 \\
0 & 1 & -\lambda & 1 & 0\\
0 & 0 & 1 & -\lambda & 1\\
0 & 0 & 0 & 1 & -\lambda
\end{array}\right)\\
&= -\lambda \det\left(\begin{array}{cccccc}
-\lambda & 1 & 0 & 0\\
1 & -\lambda & 1 & 0 \\
0 & 1 & -\lambda & 1\\
0 & 0 & 1 & -\lambda
\end{array}\right) - \det\left(\begin{array}{cccccc}
1 & 1 & 0 & 0\\
0 & -\lambda & 1 & 0 \\
0 & 1 & -\lambda & 1\\
0 & 0 & 1 & -\lambda
\end{array}\right)\\
&= -\lambda S_4 - \det\left(\begin{array}{cccccc}
-\lambda & 1 & 0 \\
1 & -\lambda & 1\\
0 & 1 & -\lambda
\end{array}\right)\\
&= -\lambda S_4 - S_3
\end{aligned}\end{align}

By induction, one can derive the following recursive relation between the terms of the sequence $S_n = \det(A-\lambda I_n)$:
\begin{align}\begin{aligned}
S_1 &= -\lambda\\
S_2 &= \lambda^2-1\\
S_n &= -\lambda S_{n-1} - S_{n-2},\quad \text{ for all }n\geq 3
\end{aligned}\end{align}
To prove this, one only needs use what I did in the first few terms as a guideline:
First, cofactor expansion of $S_{n}$ along the first row, which yields two determinants, the first of which you should recognize as $S_{n-1}$ (it will have a multiplicative factor of $(-\lambda)$ out front from the cofactor expansion). Second, cofactor expansion of the second term along the first column, and the second term should now be recognizable as $S_{n-2}$.

In response to the comment, the recurrence is the easy part. If you have access to a symbolic mathematics engine (like Mathematica), you can implement the recurrence easily and compute it for your desired $n$. However, once you need to solve it, there aren't a lot of easy ways to do this. One reference I might point you to is this paper about Toeplitz matrices (your matrix is a special case of this).
In this, they state (Proposition 2.1, with $a=0$) the eigenvalues are (adapting to your specific case)
$$\lambda_k = -2\cos(k\pi/(n+1))$$
where $n$ is the same $n$ from the recurrence relation and $1\leq k \leq n$. However, their proof relies on a working knowledge of Chebyshev polynomials of the first kind, which may not be that helpful.
Additionally, they provide a number of references which may or may not be helpful, but what you're looking for specifically is the eigenvalues of a Toeplitz matrix.
Also, this might be relevant.
This post from MO might be relevant.
A: The matrix $A$ can be written as the product of three matrices as follows:
$$A=\begin{pmatrix}
e_2 & e_1 & e_4 & e_3 & e_6 & e_5 & \dots
\end{pmatrix}
\begin{pmatrix}
e_1\\
e_2\\
e_3\\
e_2+e_4\\
e_5\\ 
e_4 + e_6\\ \vdots
\end{pmatrix}
\begin{pmatrix}
e_1 + e_3\\
e_2\\
e_3+ e_4 \\
e_4\\ e_5+e_5\\e_6\\\vdots
\end{pmatrix}$$
where $e_n$ is the standard $nth$ vector.
The first matrix is orthogonal matrix, the second matrix is lower triangular and the third is upper triangular. Can you figure out the eigenvalues now (hint: look at the diagonal of the 2nd and 3rd matrix)
