Categories of Bad Strings

This section discusses the categorization and recurrence relations of bad strings, particularly those that do not contain the substring '000'.

The section explains how to derive recurrence relations for the number of bit strings of a given length that exclude specific substrings like '000'. It provides detailed examples of categorizing valid sequences of bits and developing relationships between these categories, illustrating how to count valid configurations through structural analysis.

Categories of Bad Strings

In this section, we explore the notion of bad strings—specifically, binary strings that do not contain the substring '000'. The focus lies in developing a recurrence relation for the number of such strings, denoted as $S(n)$.

Key Ideas:

1. Definition of Bad Strings: A bad string does not include '000' as a substring. We need to count the number of possible strings of length $n$ that adhere to this restriction.

2. Recurrence Relation: Instead of counting strings that do not contain '000' directly, a more efficient approach is to formulate the count in terms of other simpler categories.

3. Categorization:

   • Category 1: Strings starting with '1'—if the string starts with '1', the subsequent bits can form any valid sequence of length $n-1$ without '000'. This contributes $S(n-1)$ to the count.
   • Category 2: Strings starting with '01'—the remaining string of length $n-2$ must also not contain '000'. This adds $S(n-2)$ to the count.
   • Category 3: Strings starting with '00'—if the third position can only be '1' (to avoid forming '000'). This situation yields contributions from strings of length $n-3$, thus adding $S(n-3)$ to the equation.

Through summation of these categories, the recurrence relation can be expressed as follows:

$S(n) = S(n-1) + S(n-2) + S(n-3)$

4. Initial Conditions: The recurrence relations require initial conditions for proper calculation. The string lengths yield the conditions:
   • $S(1) = 2$ (strings: '0', '1')
   • $S(2) = 4$ (strings: '00', '01', '10', '11')
   • $S(3) = 7$ (strings: '000' excluded, hence '001', '010', '011', '100', '101', '110', '111')

Thus, we can compute any $S(n)$ based on previously computed values using the established recurrence relation.