13.2. Example of Bit Strings without Consecutive 0's

Try these first

1. 1.

   What is C(1)?

   Hint

   Consider the valid strings of length 1.

2. 2.

   List the valid bit strings of length 2.

   Hint

   Remember that two consecutive zeros are not allowed.

3. 3.

   What is C(2)?

   • 1
   • 2
   • 3

   Hint

   Count the valid strings of two bits.

4. 4.

   C(n) is defined as?

   • True
   • False

   Hint

   Remember what our function counts.

5. 5.

   Using the recurrence relation, calculate C(6) and validate your answer.

   Hint

   Don’t forget to use the previous two values you computed.

6. 6.

   Create a program that generates all possible n-bit strings and filters out those containing consecutive 0's. Verify its output for n = 5.

   Hint

   Try using recursive functions for bit generation.