Find all $scattered$ numbers less than $2^n$ whose in its binary expansion there are never two 1's immediately next to each other

Question

Any positive integer can be written in binary (also called base $2$ ). For example, $37$ is $100101$ in binary ( because $37=2^5+2^2+2^0)$, and $45$ is $101101$ in binary. Let's say that a positive integer is '$scattered$' if, in its binary expansion, there are never two ones immediately next to each other. For example, $37$ is $scattered$ but $45$ is not. How many scattered numbers are there less than $4$ ? Less than $8$ ? Less than $2^n$? I have thought it by the length of the number and made a recursion $a_n= a_{n-1}+a_{n-3}$.May be this can help. Any other help would be appreciated.

Answer 1

This answer was made possible by the significant hint given by @user2661923.

Let $\boldsymbol{f(n)}$ denote the number of scattered binary strings with $\boldsymbol{n}$ terms, and let $a_n$ denote an arbitrary scattered binary string with $n$ terms. $a_n$ can end with a $0$ or a $1$.

Suppose $a_n$ ends with a $0$. Then, we can remove the last term to produce a binary string which is still scattered. Conversely, this implies that for every $a_{n-1}$ (there are $f(n-1)$ such strings), one can form $f(n-1)$ scattered binary strings of length $n$ by concatenating a $0$.

Now, if $a_n$ ends with a $1$, then we'll have to modify our earlier reasoning. We know that the last two terms of $a_n$ will be $01$. (Note: we will not consider the case $n = 1$, where $a_n = 1$, since our recursion will start for $n \ge 3$). So, if we remove the $01$, we'll arrive at another scattered binary string of length $n-2$. Conversely, for every $a_{n-2}$ (there are $f(n-2)$ of these), one can form $f(n-2)$ strings of length $n$ by concatenating $01$.

Since we have covered all the cases, we can establish a recurrence relation. We need to calculate $f(1)$ and $f(2)$ manually, which is easy. We get: $$\color{green}{f(1) = 2}$$$$\color{green}{f(2) = 3}$$ and $$\color{green}{f(n) = f(n-1) + f(n-2) \text{ for all } n \ge 3}$$