16.2.2. Categories of Bad Strings

Try these first

1. 1.

   What is a bad string?

   Hint

   Think about what sequences you would want to exclude.

2. 2.

   How many valid strings of length 2 exist?

   Hint

   List all the possible strings of length 2.

3. 3.

   What is the characteristic of a bad string?

   • Contains '000'
   • Does not contain '000'
   • Has mixed characters

   Hint

   Remember the definition from class.

4. 4.

   True or False: All strings of length 3 contain a valid configuration based on our recurrence relation.

   • True
   • False

   Hint

   Think about examples of string patterns.

5. 5.

   Calculate and prove $S(6)$ using previous calculated values.

   Hint

   Refer back to your established pattern and apply modified counts.

6. 6.

   Find a pattern by plotting values of $S(n)$ against $n$, and deduce future terms.

   Hint

   What do the numbers suggest?