Chemins sur un octogone régulier

Soient $A$ et $E$ deux sommets diamétralement opposés d'un octogone régulier convexe. Un pion qui peut occuper tous les huit sommets de cet octogone se déplace, à chaque coup, d'un sommet à l'un des deux sommets voisins; le pion part de $A$ et le jeu se termine lorsqu'il atteint pour la première fois le point $E$.

On désigne par $a_n$ le nombre de « parties » distinctes en exactement $n$ coups se terminant en $E$. Montrer que, pour tout $k\in {\mathbb{N}}^{\ast }$,

$$a_{2k-1}=0\text{et}{a}_{2k}=\frac{{\left(2+\sqrt{2}\right)}^{k-1}-{\left(2-\sqrt{2}\right)}^{k-1}}{\sqrt{2}}.$$

Remarque : une « partie » de $n$ coups est une suite de sommets $(P_0,P_1,\cdots ,P_n)$ vérifiant les conditions suivantes :

• $P_0=A$, $P_n=E$ ;
• pour tout $i\in [[0,n-1]]$, $P_i$ est distinct de $E$ ;
• pour tout $i\in [[0,n-1]]$, $P_i$ et $P_{i+1}$ sont des sommets voisins.