Задача М595‍‍

Пусть $A$‍‍ и $E$‍‍ — две противоположные вершины правильного восьмиугольника. В вершине $A$‍‍ находится лягушка. Из любой вершины восьмиугольника, кроме вершины $E$‍,‍ лягушка может прыгнуть в любую из двух соседних вершин. Попав в вершину $E$‍,‍ лягушка останавливается и остаётся там. Пусть $a_n$‍‍ — количество способов, которыми лягушка может попасть из вершины $A$‍‍ в вершину $E$‍‍ ровно за $n$‍‍ прыжков. Докажите, что $$ a_{2n-1}=0,\quad a_{2n}=\dfrac{1}{\sqrt{2}}(x^{n-1}-y^{n-1}),$$ $n=1$‍,‍ 2, 3, $\ldots$‍,‍ где $x=2+\sqrt{2}$‍,‍ $y=2-\sqrt{2}$‍.‍