jj_ca888 wrote:

Remark: Cool problem!!! Thankfully, this was not the recursion bash I thought it would be

Also this is very similar to the solutions provided above by users TheUltimate123 and JSGandora.

Remark: Cool problem!!! Unfortunately, I couldn't find the creative solution I knew existed

Also this is very similar to the solutions provided above by user GeronimoStilton.

We first do some work to write $a_n$ in terms of a few simpler sequences. Observe that since our first move is from $A$ , we either move once or twice from $A$ . If we move twice from $A$ , we can view the sequence of moves as a pair of two moves, each of length $n$ , such that no move from the same point is the same. From here, we can discard the circle entirely and instead view the moves in terms of two horizontal bars filled with blocks of length 1 or 2 such that no two blocks are at the same length and the same spot. Here's an example:
$[asy] size(150); draw((0,0)--(6,0)--(6,1)--(0,1)--cycle); draw((0,2)--(6,2)--(6,3)--(0,3)--cycle); draw((1,0)--(1,1)); draw((2,0)--(2,1)); draw((4,0)--(4,1)); draw((2,2)--(2,3)); draw((3,2)--(3,3)); draw((5,2)--(5,3)); [/asy]$
Let the number of ways to fill a pair of bars, both with length $n$ , be $b_n$ . We will do the recursion work later. Now suppose we move once from $A$ . If we let the point counterclockwise from $A$ be $B$ , then it is clear that on the first cycle around the circle we reach $B$ , then move two points forward from there, and after that move to $A$ . Once again, we can discard the circle and view it in terms of bars, but this time the bars are offset from each other.
$[asy] size(150); draw((0,0)--(6,0)--(6,1)--(0,1)--cycle); draw((1,2)--(7,2)--(7,3)--(1,3)--cycle); draw((1,0)--(1,1)); draw((2,0)--(2,1)); draw((4,0)--(4,1)); draw((3,2)--(3,3)); draw((5,2)--(5,3)); [/asy]$
$[asy] size(150); fill((4,0)--(4,1)--(6,1)--(6,0)--cycle,red); fill((4,2)--(4,3)--(6,3)--(6,2)--cycle,red); draw((0,0)--(6,0)--(6,1)--(0,1)--cycle); draw((1,2)--(7,2)--(7,3)--(1,3)--cycle); draw((1,0)--(1,1)); draw((2,0)--(2,1)); draw((4,0)--(4,1)); draw((3,2)--(3,3)); draw((4,2)--(4,3)); draw((6,2)--(6,3)); [/asy]$
In the examples above, the upper example is valid, but the lower is not since the two red blocks are the same length at the same spot. Let the number of ways to fill these two bars of length $n$ be $c_n$ . It is clear that
$a_n=b_n+c_{n-1}.$ Finally, introduce the sequence $(d_n)$ , which counts the number of ways to fill two bars: one of length $n$ , and the other of length $n-1$ . Here's an example:
$[asy] size(150); draw((0,0)--(6,0)--(6,1)--(0,1)--cycle); draw((0,2)--(5,2)--(5,3)--(0,3)--cycle); draw((1,0)--(1,1)); draw((2,0)--(2,1)); draw((4,0)--(4,1)); draw((2,2)--(2,3)); draw((3,2)--(3,3)); [/asy]$
Now that we've defined everything, it's time to do the recursion work. First consider $c_n$ . Call the bar which is offset to the right the "right bar" and the other bar the "left bar". Consider the following cases:
Case 1: The first block in the left bar is a block of length 1. Then we clearly have $d_n$ ways to fill the remaining blocks.
Case 2: The first block in the left bar is a block of length 2, and the first in the right bar is of length 1. Then we clearly have $d_{n-1}$ ways to fill the remaining blocks.
Case 3: The first blocks in the left and right bars are both of length 2. Then we have $c_{n-2}$ ways to fill the remaining blocks.
Hence we have the recursion
$c_n=c_{n-2}+d_n+d_{n-1}.$ Now we establish a relationship between $b_n$ and $d_n$ . By inspection, we can see that in one of the bars, the rightmost block is of length 1, and in the other the rightmost block is of length 2 (anything else breaks the condition). If we delete/ignore the rightmost blocks, we then get one bar of length $n-1$ and another of $n-2$ . Since $d_n$ doesn't count alignment, but there are two distinct possiblities for orientation after deleting the rightmost blocks, we establish $b_n=2d_{n-1}$ .
Now we compute $b_n$ . Consider the leftmost distance along the block, except from the very left of the block, where two blocks both end (this must exist, since two blocks both end at the right edge of the bar). Here, this distance is marked by the red line:
$[asy] size(150); draw((0,0)--(6,0)--(6,1)--(0,1)--cycle); draw((0,2)--(6,2)--(6,3)--(0,3)--cycle); draw((1,0)--(1,1)); draw((2,0)--(2,1)); draw((4,0)--(4,1)); draw((2,2)--(2,3)); draw((3,2)--(3,3)); draw((5,2)--(5,3)); draw((2,-1)--(2,4),red); [/asy]$
It is not hard to see that it is impossible for this distance to be 1, and for any (integer) distance in $[2,n]$ there is exactly two ways to fill in the blocks to the left of this distance. Hence we have the recursion:
$b_n=2b_{n-2}+2b_{n-3}+\cdots+2b_0.$ Comparing $b_n$ and $b_{n-1}$ and subtracting, we obtain
$b_n-b_{n-1}=2b_{n-2} \implies b_n=b_{n-1}+2b_{n-2}.$ Further, it's not hard to compute $b_0=1$ (there is one way to fill in the empty bars: doing nothing), and $b_1=0$ (if necessary, you can also compute a bit more). From here, simple induction is sufficient to show that
$b_n=\frac{2}{3}(2^{n-1}+(-1)^n),$ which also gives
$d_n=\frac{1}{3}(2^n-(-1)^n).$ Using this, we can verify the identity
$b_n+b_{n-1}=2^{n-1},$ as well as
$d_n+d_{n-1}=2^{n-1} \implies c_n=c_{n-2}+2^{n-1}.$ Further, we can get $c_0=c_1=1$ , so
$\begin{align*} c_{2m}&=2^{2m-1}+2^{2m-3}+\cdots+2^1+1\\ c_{2m+1}&=2^{2m}+2^{2m-2}+\cdots+2^2+1. \end{align*}$ We're actually done now, since
$\begin{align*} a_{n-1}+a_n&=b_n+b_{n-1}+c_{n-1}+c_{n-2}\\ &=2^{n-1}+2^{n-2}+2^{n-3}+\cdots+2^2+2^1+1+1\\ &=2^{n-1}+2^{n-1}=2^n.\quad \blacksquare \end{align*}$