USAMO 2013 — Days 1 and 2 Question 2

For $n\ge3$, place $n$ equally spaced points around a circle, label one $A$, and start a marker there. Each move goes clockwise to the next point or the point after that, giving $2n$ distinct directed moves. Let $a_n$ count the ways to go around exactly twice, starting and ending at $A$, without repeating a move. Prove $a_{n-1}+a_n=2^n$ for every $n\ge4$.

Proposed by Kiran Kedlaya (as credited in the supplied compilation).