13.4. Initial Conditions for Recurrence Function

Now we want to find out what exactly will the (\text{n}) function look like or what will be the output of the function  on input $\text{n}$. And I want to set up a recurrence equation for that. That means I would like to express the value (\text{n}) in terms of the output of  function on small size inputs.

In this portion, we want to determine the recurrence function, denoted as (\text{n}), which counts the number of valid bit strings of length $n$ that do not contain consecutive zeros. The goal is to express (\text{n}) in terms of its values for smaller inputs, specifically smaller lengths of bit strings. This is crucial in establishing how the count grows as the size of the strings increases because recurrence relations help us compute values based on previously known values.

Imagine you are assembling a bracelet using beads of different colors. You want to ensure that no two beads of the same color are adjacent. If you know how many valid combinations exist for a bracelet with a few beads, you can build on that knowledge to determine the total combinations for a longer bracelet. This is similar to how we use previous counts of bit strings to calculate counts for longer strings.

However, the argument that we had holds only if $n \geq 3$. Because if I take $n = 2$, then this argument would not hold because we (0) upon substitution. (0) does not make any sense since, as per the definition of my  function, it is the number of strings of length 0 which do not have an occurrence of two consecutive 0’s.

In this chunk, we identify the limitations of our established recurrence relation. When dealing with bit strings of lengths less than 3, we cannot rely solely on our established patterns (where the count depends on previous values) because there are not enough previous values to utilize. For instance, when calculating valid strings of length 2, we must consider other factors due to the limited number of strings that can be formed.

Think of this like trying to stack blocks. If you have only two blocks, the way you can stack them is limited. You can't use previous configurations to help you stack them because there aren't enough blocks to form a pattern. In counting terms, we need specific starting conditions for different lengths.

So that is why this definition of this recursive function holds for all $n \geq 3$. So now you might be wondering what about the output of the  function on inputs which are less than 3. So we will be giving some initial conditions. They are called initial conditions because the recursive functions are not applicable for the case when $n = 1$ and $n = 2$.

In this section, we clarify the necessity of defining initial conditions for cases where $n < 3$. The recurrence relation previously described does not suffice for smaller values, hence we must specify explicitly how many valid strings exist for these lengths. For $n = 1$, both '0' and '1' are valid, leading to a count of 2; for $n = 2$, the valid strings are '00' is invalid, so the valid configurations are '01', '10', and '11', giving a count of 3.

Imagine a game where players can select from a small set of moves. If there are only a couple of options, you can't simply calculate the outcomes based on previous game scenarios since there aren't enough previous moves to consider. You have to identify these basic possibilities before building up to larger scenarios.

Because if $n = 1$, then the number of bit strings of length 1 which do not have an occurrence of 2 consecutive 0’s is 2. Because both the strings, 0 as well as the string 1, will be considered as valid string. Similarly, if I consider $n = 2$ then the possible strings of length 2 which do not have occurrences of 2 consecutive 0’s are 11, 10 and 01. These are the valid strings, and how many strings do you have? 3.

In this part, we finalize the initial conditions by stating explicitly what outputs to expect when calculating for the smallest sizes. For $n = 1$, the valid strings can only be either '0' or '1', which confirms that (1) = 2. For $n = 2$, the valid strings '11', '10', and '01' bring us to (2) = 3. These outputs are vital for helping to kickstart the recurrence relation for any input greater than or equal to 3.

Think of this as starting a journey where the first few places to visit are limited to just two or three locations. You clearly have to define where those starting points are before determining the path as you head towards multiple destinations.

--