Question 9
(FRG 4) IMO6. Let $S$ and $F$ be two opposite vertices of a regular octagon. A counter starts at $S$ and each second is moved to one of the two neighboring vertices of the octagon. The direction is determined by the toss of a coin. The process ends when the counter reaches $F$. We define $a_n$ to be the number of distinct paths of duration $n$ seconds that the counter may take to reach $F$ from $S$. Prove that for $n=1,2,3,\ldots$,
$$a_{2n-1}=0,\qquad a_{2n}=\frac1{\sqrt2}(x^{n-1}-y^{n-1}),\qquad x=2+\sqrt2,\quad y=2-\sqrt2.$$
$$a_{2n-1}=0,\qquad a_{2n}=\frac1{\sqrt2}(x^{n-1}-y^{n-1}),\qquad x=2+\sqrt2,\quad y=2-\sqrt2.$$