How do I solve this problem?

Question

Any positive integer can be written in binary (also called base 2). For example, 37 is 100101 in binary (because 37 = 25 + 22 + 2º), and 45 is 101101 in binary. Let's say that a positive integer is “scattered” if, in its binary expansion, there are never two 1s 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 2n?

Answer 1

less than 4 means 3, 2 or 1

3 base 10 = 2+1 = 2^1 + 2^0 = 11 binary

2 base 10 = 2^1 + (0)2^0 = 10 binary

1 base 10 = 1 binary

11 is not scattered, 10 and 1 are, 2 scattered integers less than 4

less than 8 means 7,6,5,4,3,2 or 1

7 = 4+2+1 = 2^2+2^1+2^0= 111 which is Not scattered

6 = 4+2+0 = 110 Not scattered

5= 4+1 = 2^2 + 2^0 = 101 scattered

4 = 2^2 = 100 scattered

that's 4 scattered less than 8, 3 Not scattered

less than 2 means 1 or less, 1 is scattered

pattern seems to be 1,2,4,8,..2^n ...scattered

for less than 2,4,8,16, ... 2n

less than 2n then has 2^n scattered