16.2.4. Initial Conditions for Bad Strings

In question 2 you have to find out the recurrence relation for the number of bit strings of length $n$ that contain the substring "000". It might have more than 1 occurrence of "000" as well. In fact, a string of length $n$ consisting of all 0’s is a valid string. So let’s try to find out this by formulating a recurrence equation. So let $B_n$ denote the number of bit strings of length $n$ containing the substring "000".

In this section, we are focusing on counting bit strings of a specific length that contain a certain sequence ('000'). This is a common problem in combinatorics, where we want to understand combinations and arrangements of items (in this case, bits) that meet certain criteria. The function $B_n$ will help capture the count based on the length of the string, and we will later derive its behavior using recurrence relations.

Imagine you are creating a password to access a system. The password must consist of a combination of zeros and ones, but it must not contain '000' in a row. This situation is analogous to the problem we're exploring with bit strings, where you want to find how many valid passwords (bit strings) can be created that do not have three consecutive zeros.

So our goal now will be boiling down to find out the recurrence condition for the $B$ sequence. And it turns out that there are 3 disjoint categories of bit strings of length $n$ not containing "000". Let us look into those 3 categories. Category 1 consists of those strings of length $n$ that start with 1. If it starts with 1, then in order that the overall string does not have any occurrence of "000", it should be the case that the remaining portion, namely the remaining portion of length $n - 1$ bits, should not have any occurrence of "000". How many such strings we can have? As per our definition of $B$ function, there will be $B_{n-1}$ such strings.

In this chunk, we break down our bad strings into three categories based on their starting bits. The first category covers all strings that start with a '1', which eliminates the immediate possibility of starting with '000'. Therefore, we only need to focus on the remaining substring of length $n - 1$ to see if it can be valid (i.e., also not contain '000'). This leads to a new recurrence that starts to construct our understanding of valid sequences.

Think of a rule in a game where you can only start your turn with a certain action, like saying 'Go' instead of starting with 'Stop'. In relation to our problem, starting with '1' is like saying 'Go', allowing flexibility in the remaining sequences without immediately hitting a 'Stop'.

Category 2 of bad strings are those that start with "01" and if that is the case, then the remaining $n - 2$ bit positions should not have any occurrence of "000". How many such bit strings can we have? We can have $B_{n-2}$ such strings. And Category 3 of bad strings where the first two positions are 0, and in that case, the third position cannot be 0 because if the third position has a 0 then it is not a bad string. The definition of a bad string is that it should not have any occurrence of "000".

Here, we define the second and third categories based on how we start the string. The second category is for strings that begin with "01", as these can safely append valid sequences of length $n-2$. The third category, on the other hand, allows two '0's at the start, but with limitations imposed to prevent the formation of '000'. This classification is crucial for our next steps of combining these insights into a recurrence relation.

Imagine a shop where you can only start your day either by summoning customer '1' or customer '01'. If you start with '01' (like saying hello to someone by their full name), your interactions should not lead to confusion (no more than two consecutive zeros in customer actions). Similarly, we maintain rules about the sequence we allow.

So how many bad strings of length $n$ can we have? The number of bad strings of length $n$ will be the summation of the number of bad strings of length $n-1$, $n-2$, and $n-3$. Hence we get this recurrence equation for the $B$ series. And since this is an equation of degree 3, we need 3 initial conditions. $B_1 = 0$ because there are no 1-bit strings that can contain "000", similarly, $B_2 = 0$, and $B_3 = 1$.

This is where we finalize our recurrence relation based on our analysis of the different categories of bad strings. By summing up each category's contributions, we're effectively determining the total number of configurations of strings of length $n$. Establishing the initial conditions is vital for solving the recurrence; we've found our basic cases based on lengths where it would be impossible or possible to have those substrings.

Think of it like counting the total number of arrangements of different colored beads. If you only have one or two beads, they can’t create the pattern you're requiring ('000'), so they don't count. However, once you have enough beads (3 or more), you start to have a valid arrangement that meets your needs.

--