Answer:
144
Step-by-step explanation:
For a bitstring of length n, there are Fibonacci(n+2) strings containing no two consecutive zeros. This can be seen by constructing the strings starting with n=1.
1-bit strings: 1, 0 -- 2 strings not containing consecutive 0s
2-bit strings: 11, 10, 01 -- 3 strings not containing consecutive 0s
Note that we have added 1 to all the 1-bit strings, and added 0 only to the string ending in 1.
3-bit strings: 111, 110, 101, 011, 010 -- 5 strings not containing consecutive 0s
Note that these 5 strings consist of all (3) of the 2-bit strings with 1 appended, and all (1) of the 2-bit strings ending in 1 with 0 appended. The number that now end in 0 is the number previously ending in 1.
__
If (x, y) represents the numbers of n-bit strings ending in (0, 1), then the number of (n+1)-bit strings ending in (0, 1) is (y, x+y). That is, the recursive relation is ...
For n=1 to n=10, these pairs are ...
(1, 1), (1, 2), (2, 3), (3, 5), (5, 8), (8, 13), (13, 21), (21, 34), (34, 55), (55, 89)
The sequence of b[n] values is ...
2, 3, 5, 8, 13, 21, 34, 55, 89, 144
which are the n=3 to n=12 numbers from the Fibonacci sequence.
That is, there will be Fibonacci(12) = 144 10-bit strings with no consecutive 0s.
