Solution 1 (By Sam Vandervelde). We will show that $a_n = \frac{1}{3}(2^{n+1} + (-1)^n)$. This would be sufficient, since then we would have
$$a_{n-1} + a_n = \frac{1}{3}(2^n + (-1)^{n-1}) + \frac{1}{3}(2^{n+1} + (-1)^n) = \frac{1}{3}(2^n + 2 \cdot 2^n) = 2^n.$$

Lemma 1. For all positive integers $n$, we have
$$\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k} 2^k = \frac{1}{3}(2^{n+1} + (-1)^n).$$
Proof. We argue by strong induction. To begin, the cases $n = 1$ and $n = 2$ are quickly verified. Now suppose that $n \ge 3$ is odd, say $n = 2m + 1$. We find that
$$\begin{aligned} \sum_{k=0}^{m} \binom{2m+1-k}{k} 2^k &= 1 + \sum_{k=1}^{m} \binom{2m-k}{k} 2^k + \sum_{k=1}^{m} \binom{2m-k}{k-1} 2^k \\ &= \sum_{k=0}^{m} \binom{2m-k}{k} 2^k + 2 \sum_{k=0}^{m-1} \binom{2m-1-k}{k} 2^k \\ &= \frac{1}{3}(2^{2m+1} + 1) + \frac{2}{3}(2^{2m} - 1) \\ &= \frac{1}{3}(2^{2m+2} - 1), \end{aligned}$$

We now determine the number of ways to advance around the circle twice, organizing our count according to the points visited both times around the circle. It is straight-forward to check that no two such points may be adjacent, and that there are exactly two sequences of moves leading from any such point to the next. (These sequences involve only moves of length two except possibly at the endpoints.) Hence given $k \ge 1$ points around the circle, no two adjacent and not including point $A$, there would appear to be $2^k$ ways to traverse the circle twice without repeating a move. However, half of these options lead to repeating the same route twice, giving $2^{k-1}$ ways in actuality. There are $\binom{n-k}{k}$ ways to select $k$ nonadjacent points on the circle not including $A$ (add an extra point behind each of $k$ chosen points), for a total contribution of
$$\sum_{k=1}^{\lfloor n/2 \rfloor} \binom{n-k}{k} 2^{k-1} = \frac{1}{2} \left[ -1 + \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k} 2^k \right] = \frac{1}{6} (2^{n+1} + (-1)^n) - \frac{1}{2},$$
where we used Lemma 1 in the last step.
On the other hand, if the $k \ge 1$ nonadjacent points do include point $A$ then there are $\binom{n-k-1}{k-1}$ ways to choose them around the circle. (Select $A$ but not the next point, then add an extra point after each of $k-1$ selected points.) But now there are actually $2^k$ ways to circle twice, since we can choose either move at $A$ and the subsequent points, then select the other options the second time around. Hence the contribution in this case is
$$\sum_{k=1}^{\lfloor n/2 \rfloor} \binom{n-k-1}{k-1} 2^k = 2^{\lfloor (n-2)/2 \rfloor} \sum_{k=0}^{\lfloor (n-2)/2 \rfloor} \binom{n-2-k}{k} 2^k = \frac{2}{3}(2^{n-1} + (-1)^n),$$
where we again used Lemma 1.
Finally, if $n$ is odd then there is one additional way to circle in which no point is visited twice by using only steps of length two, giving a contribution of $\frac{1}{2}(1 - (-1)^n)$. Therefore the total number of paths is
$$\frac{1}{6}(2^{n+1} + (-1)^n) - \frac{1}{2} + \frac{2}{3}(2^{n-1} + (-1)^n) + \frac{1}{2}(1 - (-1)^n),$$
which simplifies to $\frac{1}{3}(2^{n+1} + (-1)^n)$, as desired.

Solution 2 (By Kiran Kedlaya). We give a bijective proof of the identity
$$a_n = a_{n-1} + 2a_{n-2},$$
which immediately implies that $a_n + a_{n-1} = 2(a_{n-1} + a_{n-2})$. Since trivially $a_0 = a_1 = 1$ (or alternatively $a_1 = 1, a_2 = 3$), the desired identity will then follow by induction on $n$.

To construct the bijection, it is convenient to introduce some alternate representations for the sequences we are counting. Label the points $P_0, \dots, P_{n-1}$ in order, and define $P_{i+n} = P_i$. One can then represent the sequences to be counted by listing the sequence of vertices $P_{i_0}, P_{i_1}, \dots, P_{i_m}$ visited by the marker, with the conventions that $i_0 = 0, i_m = 2n$, and $i_{j+1} - i_j \in \{1, 2\}$ for $j = 0, \dots, m-1$. One can represent such sequences of vertices in turn by $2 \times (n+1)$ matrices $A$ by setting
$$A_{ij} = \begin{cases} 1 & P_{ni+j} \text{ is visited} \\ 0 & P_{ni+j} \text{ is not visited} \end{cases} \quad \text{for } i=0,1; j=0, \dots, n.$$
Such a matrix $A$ corresponds to a valid sequence if and only if $A_{00} = A_{1n} = 1$ (so the sequence of steps starts and ends at $P_0$), $A_{0n} = A_{n0}$ (so the sequence of steps is well-defined at $P_n$), and there are no submatrices of any of the forms
$$(0 \ 0), \quad \begin{pmatrix} 0 \\ 0 \end{pmatrix}, \quad \text{or} \quad \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$$
to exclude steps of length greater than 2, duplication of a length 2 step, and duplication of a length 1 step. For example, the valid sequences for $n = 3$ are represented by the matrices
$$\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{pmatrix}.$$
Let $S_n$ be the set of valid $2 \times (n+1)$ matrices. The correspondence $S_{n-2} \sqcup S_{n-1} \sqcup S_{n-2} \sqcup S_{n-1} \cong S_n$ can then be described by replacing the right end of the matrix in the following fashion, where $\cdots$ represents any row of length $n-2$.
$$\begin{align*} \begin{pmatrix} \cdots & 1 \\ \cdots & 1 \end{pmatrix} &\mapsto \begin{pmatrix} \cdots & 1 & 1 & 1 \\ \cdots & 1 & 0 & 1 \end{pmatrix}, \begin{pmatrix} \cdots & 1 & 0 & 1 \\ \cdots & 1 & 1 & 1 \end{pmatrix} \\ \begin{pmatrix} \cdots & 0 \\ \cdots & 1 \end{pmatrix} &\mapsto \begin{pmatrix} \cdots & 0 & 1 & 0 \\ \cdots & 1 & 0 & 1 \end{pmatrix}, \begin{pmatrix} \cdots & 0 & 1 & 0 \\ \cdots & 1 & 1 & 1 \end{pmatrix} \\ \begin{pmatrix} \cdots & 0 & 1 \\ \cdots & 1 & 1 \end{pmatrix} &\mapsto \begin{pmatrix} \cdots & 0 & 1 & 1 \\ \cdots & 1 & 0 & 1 \end{pmatrix} \\ \begin{pmatrix} \cdots & 1 & 1 \\ \cdots & 0 & 1 \end{pmatrix} &\mapsto \begin{pmatrix} \cdots & 1 & 0 & 1 \\ \cdots & 0 & 1 & 1 \end{pmatrix} \\ \begin{pmatrix} \cdots & 1 & 0 \\ \cdots & 1 & 1 \end{pmatrix} &\mapsto \begin{pmatrix} \cdots & 1 & 1 & 0 \\ \cdots & 1 & 0 & 1 \end{pmatrix} \\ \begin{pmatrix} \cdots & 1 & 0 \\ \cdots & 0 & 1 \end{pmatrix} &\mapsto \begin{pmatrix} \cdots & 1 & 1 & 0 \\ \cdots & 0 & 1 & 1 \end{pmatrix} \end{align*}$$
From this description, it is easy to see that passing from one side to the other preserves the boundary condition and the excluded submatrix conditions (because every submatrix whose entries are not all shown remains unchanged). We thus have the claimed bijection.

Solution 3 (By Kiran Kedlaya). We maintain the notation used in the second solution.
We first solve a related but simpler counting problem. Let $S_n$ be the set of sequences of steps of lengths 1 or 2 of total length $n$. For each sequence $s \in S_n$, let $b(s)$ be the number of steps of length 2 in $s$ and define $f_n = \sum_{s \in S_n} 2^{b(s)}$. It is clear that $f_0 = f_1 = 1$. For $n \ge 2$, we also have
$$f_n = f_{n-1} + 2f_{n-2}$$
by counting sequences of length $n$ according to whether they end in a step of length 1 or 2. Thus
$$f_n + f_{n-1} = 2(f_{n-1} + f_{n-2}),$$
from which it follows by induction on $n$ that $f_n + f_{n-1} = 2^n$ for $n \ge 1$. Again by induction on $n$, we find that
$$f_n = \frac{2^n + (-1)^n}{3}.$$
We now write $a_n$ in terms of $f_n$. Label the points of the circle as in the previous solution. We may separate sequences of moves into three types.

1. Sequences that visit $P_n$ but not $P_{n-1}$. Such a sequence starts with some $s \in S_{n-2}$ followed by a step of length 2. The number of complements for $s$ (i.e., the number of ways to complete it to a full sequence) can be seen to be $2^{b(s)}$ as follows. If we decide in order whether to skip each of $P_{n+1}, \dots, P_{2n}$, then the choice for $P_{n+i}$ is uniquely forced if $A_{0(i-1)} = 1$ and unrestricted if $A_{0(i-1)} = 0$. In the notation of the previous solution, we may see this by noting that
$$\begin{pmatrix} A_{0(i-1)} & A_{0i} \\ A_{1(i-1)} & A_{1i} \end{pmatrix} \in \left\{ \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \right\}.$$
(This logic does not apply to $P_{2n}$: we have $A_{0(n-1)} = 0$ but must take $A_{1(2n)} = 1$.) We thus get $f_{n-2}$ sequences of this type.
2. Sequences that visit $P_{n-1}$ but not $P_n$. Such a sequence starts with some $s \in S_{n-1}$ followed by a step of length 2. There are $f_{n-1}$ sequences of this type.
3. Sequences that visit both $P_{n-1}$ and $P_n$. Such a sequence starts with some $s \in S_{n-1}$ followed by a step of length 1. Here the count is complicated by the constraint that we must skip $P_{2n-1}$, so the final step of length 2 does not create an option. Therefore, $s$ contributes $2^{b(s)-1}$ complements if $b(s) > 0$. The only case where $b(s) = 0$ is when $s$ consists of only steps of length 1, in which case we get 1 complement if $n$ is even and 0 complements if $n$ is odd.
Putting this together, we get
$$\begin{align*} a_n &= f_{n-2} + f_{n-1} + \frac{1}{2}(f_{n-1} + (-1)^n) \\ &= \frac{2^{n-2} + (-1)^{n-2}}{3} + \frac{2^{n-1} + (-1)^{n-1}}{3} + \frac{2^{n-1} + (-1)^{n-1}}{6} + \frac{(-1)^n}{2} \\ &= \frac{2^n + (-1)^n}{3}, \end{align*}$$
and so $a_{n-1} + a_n = 2^n$ as desired.

Solution 4 (By Ricky Liu). We again show that $a_n = \frac{1}{3}(2^{n+1} + (-1)^n)$. First, we claim that for two paths to travel between points $k$ apart ($k > 1$) such that no point in between the endpoints is in both paths and no move is used twice, one path must hit the odd intermediate points and the other must hit the even ones. Indeed, neither path can skip two consecutive points, hence neither can contain two consecutive points which are not endpoints, yielding the desired classification. Therefore, given an interval of length $k > 1$ with both endpoints hit both times around, but no point in between them hit both times around, there are exactly 2 ways to choose the sections of the path between the two endpoints (by choosing whether the odd or even points are hit first). We conclude that the generating function for choices of paths between points $k$ apart which are hit both times around is
$$f(x) = 2x^2 + 2x^3 + \dots = \frac{2x^2}{1-x}$$
Any pair of paths that start and end at the same point such that no move is used more than once are a concatenation of some number of the paths above, hence the generating function for choices of such paths is
$$g(x) = f(x) + f(x)^2 + f(x)^3 + \dots = \frac{f(x)}{1-f(x)} = \frac{2x^2}{1-x-2x^2}.$$
Note that the coefficient of $x^n$ in $g(x)$ counts the number of solution paths that stop at $A$ the first time around.

Now, any solution path that does not stop at A the first time around either (A) does not stop at any point twice or (B) has a first point $P$ and a last point $Q$ where it stops twice (where possibly $P = Q$). Case (A) is only possible if all moves have length 2 and $n$ is odd, so it has generating function $h(x) = \frac{x}{1-x^2}$. For Case (B), a similar argument to the first shows that the part of the path outside of the interval $[P, Q]$ is uniquely determined. The generating function for the number of such paths is
$$r(x) = \left(\frac{x}{1-x}\right)^2 \cdot (1 + f(x) + f(x)^2 + \dots) = \left(\frac{x}{1-x}\right)^2 \frac{1-x}{1-x-2x^2} = \frac{x^2}{(1-x)(1-x-2x^2)},$$
where the first term comes from the part before $P$ and the part after $Q$ and the second term from the interval between $P$ and $Q$.
Adding up our generating functions in each case, we find that the generating function for paths of the desired form is
$$g(x) + h(x) + r(x) = \frac{2x^2}{1-x-2x^2} + \frac{x}{1-x^2} + \frac{x^2}{(1-x)(1-x-2x^2)} = \frac{4}{3}\frac{x}{1-2x} - \frac{1}{3}\frac{x}{1+x}.$$
Then $a_n$ is the coefficient of $x^n$ in this expression, which is given by
$$a_n = \frac{4}{3}2^{n-1} - \frac{1}{3}(-1)^{n-1} = \frac{1}{3}(2^{n+1} + (-1)^n).$$