Problem

Source: Brazil Cono Sur TST 2020

Tags: analytic geometry, combinatorics



A flea is, initially, in the point, which the coordinate is $1$, in the real line. At each second, from the coordinate $a$, the flea can jump to the coordinate point $a+2$ or to the coordinate point $\frac{a}{2}$. Determine the quantity of distinct positions(including the initial position) which the flea can be in until $n$ seconds. For instance, if $n=1$, the flea can be in the coordinate points $1,3$ or $\frac{1}{2}$.