16.2. Bit Strings with Substring '000'

Try these first

1. 1.

   What is the total number of bit strings of length 1?

   Hint

   Think of all possible combinations of 0s and 1s.

2. 2.

   Provide the valid strings of length 2 without '000'.

   Hint

   List all combinations of 2 bits.

3. 3.

   What is B(n)?

   Hint

   Consider what B(n) represents in our earlier explanations.

4. 4.

   How many bits strings of length 3 are valid for A(3)?

   • 1
   • 2
   • 4
   • 7

   Hint

   Count the valid strings without the substring '000'.

5. 5.

   Determine the number of valid bit strings of length 6 without the substring '000'.

   Hint

   Ensure you use A(3), A(4), and A(5) correctly.

6. 6.

   If n grows larger, what would be the limiting behavior of the ratio B(n)/A(n)? Explain.

   Hint

   Think about the overall growth patterns of Fibbonaci-like sequences.