Formula for determinant For $n \geq 2$, let $_$ be the $n \times n$ matrix defined by
$(G_n)_{ij} = 1 \text{ if } i = j$
$(G_n)_{ij} = 2 \text{ if } j = i + 1$ (mod n)
$(G_n)_{ij} = 0$ otherwise
I am told there is a general formula for det$(G_n)$ for $n \geq 2$. This is what I'd like to find.
I find that $G_2$ = $\begin{bmatrix} 1 & 2  \\ 2 & 1 \end{bmatrix}$ with det($G_2$) = -3.
$G_3$ = $\begin{bmatrix} 1 & 2 & 0 \\ 0 & 1 & 2  \\ 2 & 0 & 1\end{bmatrix}$ with det(G_3) = 9
$G_4$ = $\begin{bmatrix} 1 & 2 & 0 & 0 \\ 0 & 1 & 2 & 0 \\ 0 & 0 & 1 & 2 \\ 2 & 0 & 0 & 1\end{bmatrix}$ with det($G_4$) = -15
I can guess the general formula det$(G_n) = (-1)^{n+1}(2^n-1)$. How might I show that this is true for all n? As hint I was told to use the permutation definition of the determinant.
Any help would be appreciated.
edit:
Attempted proof:
I will use the fact that (1) If $\pi \in S_n$ is a permutation for which either $\pi(i) = i$ or $\pi(i) = i + 1 $(mod $n)$ holds for all i, then we either have $\pi(i) = i$ for all $i$ or $\pi(i) = i + 1 $(mod $n$) for all $i$.
Let det$(G_n) = \sum_{\pi \in S_n}sgn(\pi)\prod_{i=1}^nG_{i,\pi(i)}$.
Since $\pi(i) = i$ is only true for the identity map. The other n! - 1 permamutations must be of the form $\pi(i) = i + 1$.
We get det$(G_n) = sgn(id)(1)^n$ + $\sum_{\pi \in S_n - id }sgn(\pi)2^n = 1 - 2^n$. Note that the sum will be negative since we took out an even permutation and there will be one more odd permutation than even.
What have I messed up here?. This formula is correct for $G_2$ and $G_4$ but not $G_3$
 A: We have $G_n=I+2C$, where
$$
C=\pmatrix{0&1\\ &0&1\\ &&\ddots&\ddots\\ &&&\ddots&1\\ 1&&&&0}.
$$
By inspecting the entries of the powers of $C$, it is easy to see that $I,C,C^2,\ldots,C^{n-1}$ are linearly independent. Therefore the minimal polynomial of $C$ has degree $n$ and it coincides with the characteristic polynomial. It follows from the equality $C^n=I$ that the minimal and characteristic polynomials of $C$ are $p(x)=x^n-1$. Thus
$$
\det(G_n)=\det(I+2C)=(-2)^n\det\left(-\tfrac12I-C\right)=(-2)^np(-\tfrac12)=1-(-2)^n.
$$
A: If we want to use the permutation formula for the determinant, then it would suffice to prove the following.

Claim: If $\pi \in S_n$ is a permutation for which either $\pi(i) = i$ or $\pi(i) = i+1 \pmod n$ holds for all $i$, then we either have $\pi(i) = i$ for all $i$ or $\pi(i) = i+1 \pmod n$ for all $i$.

Proof: Suppose for the purpose of contradiction that $\pi(i_1) = i_1$ and $\pi(i_2) = i_2 + 1 \pmod n$.
Suppose without loss of generality that $i_1 > i_2$. It cannot hold that $i_1 = i_2 + 1$, or we'd have $\pi(i_1) = \pi(i_2)$. Let $S = \{i : i_2 < i < i_1\}$; note that $S$ is non-empty. Since $\pi$ satisfies the hypothesis, we must have $\pi(S) \subset S \cup \{i_1\}$. However, $\pi$ is injective, which means that
$$
\pi(S) \subset [S \cup \{i_1\}] \setminus \{\pi(i_1),\pi(i_2)\} = S \setminus \{\pi(i_2)\}.
$$
This means that $\pi(S)$ is a smaller set than $S$, which is impossible by the pigeonhole principle.

Regarding your edit:

I will use the fact that (1) If $\pi \in S_n$ is a permutation for which either $\pi(i) = i$ or $\pi(i) = i + 1 $(mod $n)$ holds for all i, then we either have $\pi(i) = i$ for all $i$ or $\pi(i) = i + 1 $(mod $n$) for all $i$.
Let det$(G_n) = \sum_{\pi \in S_n}sgn(\pi)\prod_{i=1}^nG_{i,\pi(i)}$.

So far, so good.

Since $\pi(i) = i$ is only true for the identity map. The other n! - 1 permutations must be of the form $\pi(i) = i + 1$.

This is incorrect. There is exactly one permutation $\pi$ for which $\pi(i) = i$ holds for $i = 1,\dots,n$, and there is also exactly one permutation $\pi$ for which we have $\pi(i) = i + 1 \bmod n$ for $i = 1,\dots,n$. The key fact here is that for the remaining $n! - 2$ permutations, the product $\prod_{i=1}^n G_{i,\pi(i)}$ will be zero.
With that said, the remainder of your proof is wrong since it builds on this incorrect foundation. Let $\pi_1 \in S_n$ denote the identity map, and let $\pi_2 \in S_n$ denote the map with the formula $\pi_2(i) = i + 1 \bmod n$. With the observations in the previous paragraph, we have
$$
\begin{align}
\det(G) &= \sum_{\pi \in S_n}\operatorname{sgn}(\pi) \prod_{i=1}^n G_{i,\pi(i)}
\\ & = \operatorname{sgn}(\pi_1) \prod_{i=1}^n G_{i,\pi_1(i)}
+ \operatorname{sgn}(\pi_2) \prod_{i=1}^n G_{i,\pi_2(i)} 
\\ & = 1 \cdot 1^n + (-1)^{n-1} \cdot 2^n = 1 + (-1)^{n-1} 2^n.
\end{align}
$$
To justify this, I still need to argue that $\operatorname{sgn}(\pi_2)$ is an even permutation for odd $n$ and an odd permutation for even $n$.  To see that this is the case, it suffices to note that $\pi_2$ can be implemented as a succession of the following $n-1$ transpositions:
$$
\pi_2 = \tau_{1,2} \circ \cdots \circ \tau_{n-1,n}
$$
where $\tau_{i,j}$ is the permutation that switches the $i$th and $j$th elements, but otherwise acts as the identity permutation.

An interesting observation from the alternative approach: if we use the formula for the determinant of a circulant matrix provided here, we end up with the following. Take $f$ to be the function $f(x) = 1 + 2x$, and $\omega = e^{2 \pi i/n}$. We have
$$
\begin{align}
\det(G) = \det(G^T) = \prod_{j=0}^{n-1} f(\omega^j).
\end{align}
$$
If $n$ is odd, write this as
$$
\begin{align}
\det(G) &= \prod_{j=0}^{n-1} f(\omega^j)
= f(1) \cdot \prod_{j=1}^{(n-1)/2} f(\omega^j)f(\omega^{-j})
\\ & = 3 \cdot \prod_{j=1}^{(n-1)/2}(1 + 2\omega^j)\overline{(1 + 2 \omega^j)}
\\ & = 3 \cdot \prod_{j=1}^{(n-1)/2} |1 + 2\omega^j|^2
\\ & = 3 \cdot \prod_{j=1}^{(n-1)/2} [(1 + 2\cos(2 \pi j/n))^2 + 4 \sin^2(2 \pi j/n)]
\\ & = 3 \cdot \prod_{j=1}^{(n-1)/2} [5 + 4 \cos(2 \pi j/n)].
\end{align}
$$
Apparently, this should be equal to $1 + 2^n$.
