Permutation and Combination

Question

How many $10$ - digit strings of $0's$ and $1's$ are there that do not contain any consecutive $0's$?

Answer 1

Recurrence Relation for no. of binary strings with no consecutive 0's is

$$T(n) = T(n-1) + T(n-2)$$

with $T(1) = 2, T(2) = 3$.

The reason for the recurrence is we can get an $n$ length string with no "00" by adding a "1" to any binary string with length $n-1$ and not having "00" (if we add a 0, we might form a 00), and also by adding "10" to any binary string with length $n-2.$ These two cases are mutually exclusive (no common strings as one set is ending in $1$ and other in $0$)  and also exhaustive (includes all possible strings having "00").

Now, we go bottom up to solve for $T(10).$

• $T(1) = 2, T(2) = 3$
• $T(3) = T(2) + T(1) =  2+3 = 5$
• $T(4) = 3 + 5 = 8$
• $T(5) = 13$
• $T(6) = 21$
• $T(7) = 34$
• $T(8) = 55$
• $T(9) = 89$
• $T(10) = 144$

Answer 2

For 1 digit, Strings are {0,1} =>2

For 2 digits, Strings are {11,01,10} =>3

For 3 digits, strings are {111,110,101,011,010} =>5

For 4 digits, strings are {1111,1110,1101,1011,0111,0101,1010,0110} =>8

For 5 digits, strings are {11111,11110,11101,11011,10111,01111,01011,01010,01101,01110,10110,10101,11010} =>13

-----------------------------------------------------------------------------------------------------------------------------------------------------------

Now, look at this series carefully, 2,3,5,8,13,.. <=FIBONACCI

10th term should be required answer => 144