Is there a way to find out the exact eigenvalues and eigenvectors of a real symmetric pentadiagonal Toeplitz $n\times n$ matrix with the form given below?

$$\begin{pmatrix} a & b & c & 0 & \cdots & \cdots & 0 \\ b & a & b & c & 0 & \cdots & 0 \\ c & b & a & b & c & \ddots & \vdots \\ 0 & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 0 & \ddots & \ddots & \ddots & \ddots & b & c \\ \vdots & \ddots & 0 & c & b & a & b \\ 0 & \cdots & 0 & 0 & c & b & a \end{pmatrix}$$

In particular, I'm dealing with this conjecture (verified by numerical diagonalization):

The difference of the smallest two eigenvalues are of the order $1/n^2$ if $f(k)$ has one minimum, or $1/n^3$ if $f(k)$ has two minima, where $f(k)=a+2b\cos(k)+2c\cos(2k)$ and $k\in[0,2\pi)$.

The following papers should be helpful:

1. A note for an explicit formula for the determinant of pentadiagonal and heptadiagonal symmetric Toeplitz matrices, Mohamed Elouafi, Applied Mathematics and Computation 219 (2013) 4789–4791

2. An eigenvalue localization theorem for pentadiagonal symmetric Toeplitz matrices, Mohamed Elouafi, Linear Algebra and its Applications 435 (2011) 2986–2998

I wasn't able to figure out an exact formula for eigenvalues and eigenvectors for a pentadiagonal Toeplitz matrix. Knowing them for a tridiagonal Toeplitz, though, is very helpful. (Those can be found, for example, in this paper on the sensitivity of the spectrum of a tridiagonal Toeplitz matrix.)

As you've already discovered, the eigenvalues are approximately $a+2\cos(\omega)+2\cos(2\omega)$ where $\omega=(\frac{\pi}{n+1})*i$ where $i$ is the index of the eigenvalue. In fact, $A=Q\Lambda Q^T+E$ where $A$ is the matrix you're interested in, $\Lambda$ is a diagonal matrix with approximate eigenvalues as entries along the diagonal, $Q_{ij}=\sin((\frac{\pi}{n+1})ij)$ is the matrix whose columns are the approximate eigenvectors, and $E$ is a matrix of all zeros except a $c$ in the upper left and lower right entries. The form of the eignevectors comes from the tridiagonal case. However, there are some important caveats, and they flow from the fact that $E$ might not be small in the 2-norm (relative to $A$).

Two interesting special cases are with $b=1$ and $a=c=0$, and $c=1$ and $a=b=0$. (I'll assume in the rest that $a=0$ because $a$ only represents a shift in the eigenvalues: the diagonal is a multiple of the identity and shares eigenvectors with every matrix.) With $b=1$ and $c=0$, the above eigenpairs are exact: $c=0$ means $E=0$, and we're in the tridiagonal case. With $b=0$ and $c=1$, things are more complicated. When $A$ is of even size, $n=2m$, all eigenvalues are of multiplicity 2. The eigenvalues are of $b=1$ and $c=0$ of size $m$, with each eigenvalue repeated once. The eigenvectors of $A$ are related too: they're those of $b=1$ and $c=0$ of size $m$ interleaved with zeros; the two eigenvectors for each eigenvalue are staggered with respect to one another. When $A$ is of odd size, $n=2m+1$, the eigenvalues are the union of those for $b=1$ and $c=0$ of size $m$ and size $m+1$. The eigenvectors are again interleaved with zeros.

I'm assuming by "smallest" eigenvalue you mean "most negative". If you mean "closest to 0", adjust accordingly below.

The case of even-sized $A$ with $b=0$ and $c=1$ means repeated eigenvalues, and the difference between the two smallest eigenvalues is exactly 0. With $b=\epsilon$, $c=1$, and $\epsilon\ll 1$, the difference between the two smallest eigenvalues is $O(\epsilon/n^2)$. If $\epsilon$ is independent of $n$, this fits your conjecture. However, if you make $\epsilon=1/n^2$ or $\epsilon=\exp(-n)$, then the difference will shrink much faster than your conjecture.

With odd-sized $A$ and $b=\epsilon$, $c=1$, and $\epsilon\ll 1$, the difference between the two smallest eigenvalues is $O(1/n^3)$. With an $A$ of either parity and $b=1$, $c=\epsilon$, and $\epsilon\ll 1$, the difference between the two smallest eigenvalues is $O(1/n^2)$.

Are there any other restrictions on the matrix size you're implicitly assuming? Or on the size of the entries $a$, $b$, and $c$?

A general solution for the eigenvalues of such symmetric diagonal matrix A=\begin{bmatrix} a_0 & a_1 & a_2& a_3 &......&..&..&a_{n-1} \\ a_{n-1} & a_0 & a_1& a_2& a_3 &.....&...&a_{n-2}\\ a_{n-2}& a_{n-1} &a_0& a_1& a_2& a_3&...&a_{n-3}\\ a_{n-3} & a_{n-2}& a_{n-1}& a_0& a_1& a_2&....&a_{n-4}\\ ......&.....&.....&....&....&....&.....&a_0&\\ \end{bmatrix} (n by n) can be expressed as (if $a_r=a_{n-r}$) $E_k=a_0+2a_1\cos(\frac{2k\pi}{n})+2a_2\cos(\frac{4k\pi}{n})+2a_3\cos(\frac{6k\pi}{n})+....L,$ k=1,2,3...n, where $L=2a_s\cos(\frac{2sk\pi}{n})$ if n=2s+1 and $L=(-1)^ka_{s}$ if n=2s. In this particular matrix, put $a_r=0$ for $r\ge 3$