International Mathematical Olympiad 1979 Problem 6

Let $A$ and $E$ be opposite vertices of a regular octagon. A frog starts jumping at vertex $A$. From any vertex of the octagon except $E,$ it may jump to either of the two adjacent vertices. When it reaches vertex $E,$ the frog stops and stays there. Let $a_n$ be the number of distinct paths of exactly $n$ jumps ending at $E.$ Prove that $a_{2n-1}=0,$

$$a_{2n}=\frac{1}{\sqrt{2}}(x^{n-1}-y^{n-1}),\quad n=1,2,3,\cdots,$$

where $x=2+\sqrt{2}$ and $y=2-\sqrt{2}.$

Note. A path of $n$ jumps is a sequence of vertices $(P_0,\ldots,P_n)$ such that

(i) $P_0=A, P_n=E;$

(ii) for every $i, 0\leq i\leq n-1, P_i$ is distinct from $E;$

(iii) for every $i, 0\leq i\leq n-1, P_i$ and $P_{i+1}$ are adjacent.