Problem: For a positive integer $n\geq 3$ plot $n$ equally spaced points around a circle.
Label one of them $A$, and place a marker at $A$.
One may move the marker forward in a clockwise direction
to either the next point or the point after that.
Hence there are a total of $2n$ distinct moves available; two from each point.
Let $a_n$ count the number of ways to advance around the circle exactly twice,
beginning and ending at $A$, without repeating a move.
Prove that $a_{n-1}+a_n=2^n$ for all $n\geq 4$.

Solution: We present two similar approaches.

\paragraph{First solution.}
Imagine the counter is moving along
the set $S = \{0, 1, \dots, 2n\}$ instead,
starting at $0$ and ending at $2n$, in jumps of length $1$ and $2$.
We can then record the sequence of moves as a matrix of the form
\[
  \begin{bmatrix}
    p_0 & p_1 & p_2 & \dots & p_{n-1} & p_n \\
    p_n & p_{n+1} & p_{n+2} & \dots & p_{2n-1} & p_{2n}
  \end{bmatrix}
\]
where $p_i = 1$ if the point $i$ was visited by the counter,
and $p_i = 0$ if the point was not visited by the counter.
Note that $p_0 = p_{2n} = 1$ and the upper-right and lower-left entries are equal.
Then, the problem amounts to finding the number of such matrices
which avoid the contiguous submatrices
\[
  \begin{bmatrix} 0 & 0 \end{bmatrix}
  \qquad
  \begin{bmatrix} 0 \\ 0 \end{bmatrix}
  \qquad
  \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}
\]
which correspond to forbidding jumps of length greater than $2$,
repeating a length $2$ jump and repeating a length $1$ jump.

We give a nice symmetric phrasing suggested by \texttt{fclvbfm934} at
\url{https://aops.com/community/p27834267}.
If we focus on just the three possible column vectors that appear, say
\[
  \mathbf u \coloneq \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \qquad
  \mathbf v \coloneq \begin{bmatrix} 0 \\ 1 \end{bmatrix}, \qquad
  \mathbf w \coloneq \begin{bmatrix} 1 \\ 1 \end{bmatrix}
\]
then we can instead describe valid matrices as sequences of $n+1$ such column vectors,
where no two column vectors are adjacent, and where the boundary condition is that
\begin{itemize}
  \ii either we start with $\mathbf u$ and end with $\mathbf v$, or
  \ii either we start with $\mathbf w$ and end with $\mathbf w$.
\end{itemize}
Let $x_n$ and $y_n$ denote the number of such $2 \times (n+1)$ matrices.
(Hence $a_n = x_n + y_n$.)
But owing to the symmetry of the setup with $\mathbf u$, $\mathbf v$, $\mathbf w$,
we could instead view $x_n$ (resp.\ $y_n$) as the number of $2 \times (n+1)$ matrices
for a fixed starting first column whose final column is the same (resp.\ different).
So we have the recursions
\begin{align*}
  x_{n+1} &= x_n + y_n \\
  y_{n+1} &= 2x_n.
\end{align*}
We also have that
\[ 2x_n + y_n = 2^n \]
which may either be proved directly from the recursions (using $x_1 = 1$ and $y_1 = 0$),
or by noting the left-hand side counts the total number of sequences
of $n+1$ column vectors with no restrictions on the final column at all
(in which case there are simply $2$ choices for each of the $n$ columns
after the first one).
Thus,
\begin{align*}
  a_{n+1} + a_n &= (x_{n+1} + y_{n+1}) + (x_n + y_n) \\
  &= \left( (x_n + y_n) + 2x_n \right) + (x_n + y_n) \\
  &= 2(2x_n + y_n) = 2^{n+1}
\end{align*}
as needed.

\paragraph{Second (longer) solution.}
If one does not notice the nice rephrasing with $\mathbf u$, $\mathbf v$,
$\mathbf w$ above, one may still proceed with the following direct calculation.
Retain the notation of
\[
  \begin{bmatrix}
    p_0 & p_1 & p_2 & \dots & p_{n-1} & p_n \\
    p_n & p_{n+1} & p_{n+2} & \dots & p_{2n-1} & p_{2n}
  \end{bmatrix}
\]
described earlier.
We will for now ignore the boundary conditions.
Instead we say a $2 \times m$ matrix is \emph{silver} ($m \ge 2$)
if it avoids the three shapes above.
We consider three types of silver matrices
(essentially doing casework on the last column):
\begin{itemize}
\ii \emph{type B matrices}, of the shape
  $\begin{bmatrix}
    1 & \dotsb & 1 \\
    0 & \dotsb & 0
  \end{bmatrix}$
\ii \emph{type C matrices}, of the shape
  $\begin{bmatrix}
    1 & \dotsb & 0 \\
    0 & \dotsb & 1
  \end{bmatrix}$.
\ii \emph{type D matrices}, of the shape
  $\begin{bmatrix}
    1 & \dotsb & 1 \\
    0 & \dotsb & 1
  \end{bmatrix}$.
\end{itemize}
We let $b_m$, $c_m$, $d_m$
denote matrices of each type, of size $2 \times m$,
and claim the following two recursions for $m \ge 4$:
\begin{align*}
  b_m &= c_{m-1} + d_{m-1} \\
  c_m &= b_{m-1} + d_{m-1} \\
  d_m &= b_{m-1} + c_{m-1}.
\end{align*}
Indeed, if we delete the last column of a type B matrix
and consider what used to be the second-to-last column,
we find that it is either type C or type D.
This establishes the first recursion and the others are analogous.

Note that $b_2 = 0$ and $c_2 = d_2 = 1$.
So using this recursion, the first few values are
\[
  \begin{array}{rrrrrrrr}
    m  & 2 & 3 & 4 & 5 &  6 &  7 &  8 \\ \hline
    b_m & 0 & 2 & 2 & 6 & 10 & 22 & 42 \\
    c_m & 1 & 1 & 3 & 5 & 11 & 21 & 43 \\
    d_m & 1 & 1 & 3 & 5 & 11 & 21 & 43 \\
  \end{array}
\]
and a calculation gives $b_m = \frac{2^{m-1} + 2(-1)^{m-1}}{3}$,
$c_m = d_m = \frac{2^{m-1} - (-1)^{m-1}}{3}$.

We now relate $a_n$ to $b_m$, $c_m$, $d_m$.
Observe that a matrix as described in the problem is a silver
matrix of one of two forms:
\[
  \begin{bmatrix}
    1 & p_1 & p_2 & \dots & p_{n-1} & 0 \\
    0 & p_{n+1} & p_{n+2} & \dots & p_{2n-1} & 1
  \end{bmatrix}
  \qquad
  \text{or}\qquad
  \begin{bmatrix}
    1 & p_1 & p_2 & \dots & p_{n-1} & 1 \\
    1 & p_{n+1} & p_{n+2} & \dots & p_{2n-1} & 1
  \end{bmatrix}.
\]
There are $c_{n+1}$ matrices of the first form.
Moreover, there are $2d_n$ matrices of the second form
(to see this, delete the first column;
we either get a type-D matrix
or an upside-down type-D matrix).
Thus we get
\[ a_n = c_{n+1} + 2d_n
  = \frac{2^{n+1} + (-1)^{n+1}}{3}. \]
This implies the result.

\begin{remark*}
  The two solutions are closely related.
  In fact, $c_n = x_{n-1}$ and $b_n = y_{n-1}$.
  So the second solution is really the same as the first solution,
  except the symmetry of $\mathbf u$, $\mathbf v$, $\mathbf w$ was not noticed,
  thus requiring a third recursion to handle all the cases manually.
\end{remark*}