16.3. Bit Strings with Substring '01'

In question 3, we have to find out the recurrence relation for the number of bit strings of length $n$ that contain '01'. Let $S(n)$ denote the number of bit strings of length $n$ containing '01'.

In this section, we are interested in counting the number of binary strings (strings made up of 0s and 1s) of a specified length, $n$, that must include the substring '01'. To do this, we establish a notation, $S(n)$, that clearly represents our focus. For further calculations, we will derive a recurrence relation based on properties of these strings.

Think of finding specific patterns in a sequence of steps, just like spotting a clear sign ('01') while walking through different trails in a park. You're looking for paths (bit strings) of a certain length (steps taken) that must include that sign.

There are two disjoint categories of $n$ length bit strings containing '01'. Category 1: where the string starts with '1'. If it starts with '1', the remaining $n-1$ length bit strings should also contain '01'. Category 2: where the string starts with '0'. In this case, my substrings can have one or more zeros followed by a '1'.

We categorize the strings based on their first character to manage counting effectively. In Category 1, if a string starts with '1', we need the next characters to ensure '01' appears somewhere in the remaining part of the string. In Category 2, starting with '0' means we may have trailing zeros leading up to a '1', which maintains the requirement for the '01' substring. This structured breaking down of the problem allows us to calculate possible outcomes based on these two families of strings.

Imagine entering a room: if you take a left turn first (starting with '1'), the next choices you make (remaining steps) must keep leading you to eventual pathways marked with a light bulb (the '01' sign). If you go right first (starting with '0'), your journey can include several steps before reaching another light bulb.

The recurrence relation can be expressed as $S(n) = S(n-1) + 2^{n-2}$. This is derived from adding the count of strings from both categories.

By summing the counts from both categories, we formulate the recurrence relation $S(n) = S(n-1) + 2^{n-2}$. 'S(n-1)' represents the strings starting with '1', while '2^{n-2}' accounts for all combinations of zeros after an initial '0', which ensures we still reach '01' regardless of how many zeros precede the terminal '1'. This concise formula encapsulates all valid strings of length $n$ containing '01'.

Imagine every time you cook, if you remember the dishes (bit strings) you’ve already made (S(n-1)), plus new options to try (2^(n-2) combinations), you create a new selection—the total number of meals possible becomes apparent as you combine past knowledge with new ideas.

For this recurrence relation, we need initial conditions. Specifically, $S(2) = 1$ (the string '01') and $S(3) = 2$ ('001' and '101').

To use our recurrence relation efficiently, we need base cases, which we call initial conditions. These provide specific known values for our function at the beginning of the sequence. For instance, when we have 2 bits, we only have one valid string, '01'. Extending that to 3 bits, the acceptable combinations are '001' and '101', yielding two valid strings total.

Think back to a newly opened restaurant: at the very start (S(2)), there's only one dish on the menu ('01'). But as they expand and introduce several variations (S(3)), they end up with more options—just like we are exploring valid combinations in our bit strings.

--