Question

How many 10-digit strings of 0’s and 1’s are there that do not contain any consecutive 0’s? Do not enter whitespaces before or after the answer.

Answer 1

Answer:

10 digit strings of 0's and 1's that do not contain any consecutive 0's are 144.

Step-by-step explanation:

To find : How many 10-digit strings of 0’s and 1’s are there that do not contain any consecutive 0’s?

Solution :

Let c(N) be the count of numbers with N binary digits that have no consecutive 0’s.

c(1) = 2 as 0 and 1 are not having any consecutive zeros

c(2) = 3 as 01, 10, and 11 are not having any consecutive zeros

Now, for the general case : Consider all N digit numbers.

If the first digit is 1, then the there are c(N-1) numbers that contains the remaining digits.

If the first two digits are 01, then there are c(N-2) numbers that contains the remaining digits.

In general, c(N) = c(N-1) + c(N-2).

The resulting recursion is quite similar to that of Fibonacci, but the starting conditions are quite different.

c(1) = 2,

c(2) = 3,

c(3) = 5,

c(4) = 8,

c (5) = 13,

c(6) = 21,

c(7) = 34,

c(8) = 55,

c(9) = 89,

c(10) = 144

Therefore, 10 digit strings of 0's and 1's that do not contain any consecutive 0's are c(10) = 144