Question

Let us agree to say that a non-negative integer is “scattered” if its binary expansion has no
occurence of two ones in a row. For example, 37 is scattered but 43 is not, since the binary
expansion of 37 is 100101 in which the ones are all separated by at least one zero, while the
binary expansion of 43 is 101101 which has two ones in successive places. For an integer
n ≥ 0, how many scattered non-negative integers are there less than 2n?