MathNet 2013 Câu hỏi 5

Với số nguyên dương $n \ge 3$, lấy $n$ điểm cách đều trên một đường tròn. Gọi một điểm là $A$ và đặt quân đánh dấu tại $A$. Mỗi lượt được di chuyển quân theo chiều kim đồng hồ tới điểm kế tiếp hoặc điểm cách đó hai bước. Như vậy có tất cả $2n$ nước đi khác nhau, hai nước đi từ mỗi điểm. Gọi $a_n$ là số cách đi đúng hai vòng, bắt đầu và kết thúc tại $A$, không lặp lại nước đi nào. Chứng minh $a_{n-1} + a_n = 2^n$ với mọi $n \ge 4$.
(Bài toán do Sam Vandervelde đề xuất.)