Let $n\geq 3$, let $Z$ be the matrix of the cyclic shift (the companion matrix of $X^n-1$), and for $\mathbf{d}\in \mathbb{C}^n$ let $\operatorname{diag}(\mathbf{d})$ be the diagonal matrix with $\mathbf{d}$ on the diagonal, and $$M_\mathbf{d}:=\operatorname{diag}(\mathbf{d})+Z+Z^2$$.

Notation: call a subset of $[n]:=\{1,\ldots,n\}$ separated if does not contain two (cyclically) adjacent elements, let $S_j(n):=\{ M\in [n]\;:\, |M|=j\}$ denote the set of separated subsets of $[n]$ with $j$ elements.

For $n\leq 12$ the determinant is given by: $$\det(M_{\mathbf{d}})=\sigma_n(d) +\sum_{j=0}^{n-1} (-1)^{n-j-1} \sigma_j(\mathbf{d})$$ where $\sigma_0(\mathbf{d})=\det(Z+Z^2)=\bigg\{\begin{array}{cr} 2 & \text{ for odd } n\\ 0 & \text{ for even } n\end{array}$

$\sigma_1(\mathbf{v})=d_1+\ldots+d_n$, $\sigma_n(\mathbf{v})=\prod_{i=1} d_i$, and for $2\leq j \leq n$ $$\sigma_j(\mathbf{v})= \sum_{(k_1,\ldots,k_j)\in S_j(n)}\prod_{i=1}^j d_{k_i}$$

Does the formula hold for all $n\geq 3$?

Motivation: this (and related) determinants appear in a combinatorial problem arising in homological algebra, see Classification of algebras of finite global dimension via determinants of certain 0-1-matrices