13.2. Example of Bit Strings without Consecutive 0's

Imagine I want to find out the number of n bit strings that do not have an occurrence of 2 consecutive 0's. That means the substring 00 is not allowed to appear in such a string and we want to find out how many such strings can be there.

In this section, we are looking at a specific counting problem where we want to determine the number of bit strings of length n (where n can be any positive integer) that do not have two consecutive zeros (00). This means if we create a bit string using 0's and 1's, we need to ensure that wherever we place a 0, it cannot be directly followed by another 0. Thus, valid bit strings can be like '010', '101', or '111', while '00' is forbidden.

Think of it like organizing a line of students where each student can only hold a single type of sign: either '0' or '1'. If a student with a '0' sign is first, the next student cannot also have a '0' sign. This adds a constraint to how we can form the lineup, just like the restriction on forming bit strings.

Let f(n) be a function which on input n gives you the number of n bit strings which do not have two consecutive 0's. So if I say f(1) that will give me the number of bit strings of length 1 that will not have the occurrence of 2 consecutive 0's.

Here, we define a function f(n) that specifically counts the number of valid bit strings for a given length n. For instance, f(1) represents the count of valid bit strings when there is only one bit. There are two possible strings in this case: '0' or '1', both acceptable because neither contains the substring '00'. This lays the groundwork for understanding how to compute the bit strings for longer lengths.

Imagine you are allowed to choose either a red or a blue ball to create a simple sequence. With one position, you can either pick a red ball (representing '0') or a blue ball (representing '1'). Thus, your choices are limited but clear, helping to understand constraints applied to create more complex sequences.

We want to express the value f(n) in terms of the outputs of f on smaller size inputs. If we consider any n bit string which does not have 2 consecutive 0's, then there are only 2 possibilities for the starting bit.

To find the number of valid bit strings for a length of n, we examine the first bit of the string. There are two possible scenarios: either the first bit is '1', or it is '0'. If the first bit is '1', the remainder of the string (of length n-1) must also follow the same rule regarding consecutive 0's. That gives us f(n-1) valid combinations. If the first bit is '0', then the second bit must be '1' (to prevent '00'), and we now have a valid string followed by any valid arrangement of the remaining n-2 bits, giving us f(n-2) possibilities. Thus, we establish the core recurrence relation: f(n) = f(n-1) + f(n-2).

Imagine you're making a cake with layers. The first layer can either be chocolate (1) or vanilla (0). If you start with chocolate, you can select any configuration for the remaining layers. If you start with vanilla, the next must be chocolate, adding a layer of variety depending on what you chose first, mirroring how the strings are formed.

For n < 3, we need to establish some initial conditions. For n = 1, there are 2 strings: '0', '1'. For n = 2, the valid strings are '11', '10', '01', totaling 3.

Establishing initial conditions helps frame our recurrence relation correctly to avoid any undefined scenarios. For n = 1, we have two single-bit strings: '0' and '1', hence f(1) = 2. For n = 2, we see all bit combinations but must exclude '00', leaving us with three valid strings: '11', '10', and '01', so f(2) = 3. This prepares a foundation for calculating values of f(n) for larger n using the previously established relationships.

Think of these initial values as the starting points in a game. For example, if you begin with one or two tokens, you can only create limited combinations with those tokens, guiding your larger strategy of how you'd create further combinations in the future rounds.

Thus, for n ≥ 3, we conclude the formula f(n) = f(n-1) + f(n-2), with initial conditions f(1) = 2 and f(2) = 3.

We have developed a recurrence relation that aids not only in counting the valid bit strings but also relies on previously calculated values to build up to larger strings. The formula f(n) = f(n-1) + f(n-2) for all n ≥ 3 streamlines the calculation process, transforming the problem into a more manageable iterative task based on simpler components. We can now recursively calculate any value of f(n), adhering to the initial conditions defined.

This is akin to building staircases: to reach the nth step, you can step from either (n-1)th or (n-2)th steps. Thus, once you know how many ways you can reach the first and second steps, those paths can be leveraged to find the ways to reach any higher step in the staircase, demonstrating a simple recursive structure in counting paths.

--