TUYMAADA 2022 J8

Eight poles stand along the road. A sparrow starts at the first pole and once in a minute flies to a neighboring pole. Let $a(n)$ be the number of ways to reach the last pole in $2n + 1$ flights (we assume $a(m) = 0$ for $m < 3$ ). Prove that for all $n \ge 4$ $$a(n) - 7a(n-1)+ 15a(n-2) - 10a(n-3) +a(n-4)=0.$$ (T. Amdeberhan, F. Petrov )