Олимпиада Туймаада по математике. Младшая лига. 2022 год

Вдоль дороги стоит 8 столбов. Воробей стартует с первого столба, каждую минуту он перелетает на один из соседних. Пусть $a(n)$ — количество способов через $2n+1$ перелётов оказаться на последнем столбе (считаем, что $a(m)=0$ при $m<3$). Докажите, что $a(n)-7a(n-1)+15a(n-2)-10a(n-3)+a(n-4)=0$ при всех $n\geq 4$. ( Ф. Петров, Т. Амдеберхан )