VN-TST 2019 Problem 6

In the real axis, there is bug standing at coordinate $x=1$ . Each step, from the position $x=a$ , the bug can jump to either $x=a+2$ or $x=\frac{a}{2}$ . Show that there are precisely $F_{n+4}-(n+4)$ positions (including the initial position) that the bug can jump to by at most $n$ steps.

Recall that $F_n$ is the $n^{th}$ element of the Fibonacci sequence, defined by $F_0=F_1=1$ , $F_{n+1}=F_n+F_{n-1}$ for all $n\geq 1$ .