Q9 Matemática  (IMO Shortlist 1979)

Sejam $A$ e $E$ vértices opostos de um octógono. Um sapo começa no vértice $A.$ De qualquer vértice, exceto $E$, ele pula para um dos dois vértices adjacentes. Quando atinge $E$, ele para. Seja $a_n$ o número de caminhos distintos de exatamente $n$ saltos que terminam em $E$. Prove que: $$a_{2n-1}=0,a_{2n}=\frac{(2+\sqrt{2}{)}^{n-1}-(2-\sqrt{2}{)}^{n-1}}{sqrt2}.$$