Question 6
A bug starts at coordinate $x=1$ on the real number line. At each jump, from $x=a$ it may move to $x=a+2$ or $x=a/2$. Prove that the number of distinct positions, including the initial position, reachable in at most $n$ jumps is $F_{n+4}-(n+4)$, where $F_0=F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ for $n\ge2$.