There is a row of n chairs, each containing a student. Let an be the number of ways to reassign seats so that each student either stays in place or moves only one chair to the left or right. For example, if n=3, and the people are ABC in that order, then the legal seat assignments are ABC (we do count the case where no one moves), ACB, and BCA. So a3=3.
a) Use a combinatorial argument to show that an = an-1 + an-2 for a ≥ 3. (Hint: what happens to a person on the end of the row?)
b) Prove that an is a Fibonacci number for every n.