MathDB

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

Problem Statement