13.3. Setting up the Recurrence Equation

So it turns out that there are plenty of instances or counting problems which gets significantly simplified by recurrence equations. And to recap, what exactly is a recurrence equation? So you must have encountered different equations of the following form: f(n)! = n * f(n−1). So this is a recursive function in the sense that the value of the factorial function on input n is expressed in terms of the value of the factorial function on smaller inputs.

Recurrence equations are mathematical expressions that define a function based on its values at previous points. They simplify complex counting problems by breaking them down into smaller, manageable problems. Here, the example of a factorial function is given, which states that the factorial of a number n can be derived from the factorial of n-1, multiplied by n. This recursive relationship is foundational in counting and combinatorial mathematics.

Imagine you're stacking boxes so that each box above a stack must be slightly smaller than the one below. The total number of ways to stack these boxes could depend on how you stacked the previous boxes. The idea of using previous arrangements to calculate the current one is similar to how recurrence equations work in mathematics.

So our idea here will be that now we would like to count the number of things by formulating recurrence equations. And later we will discuss how to solve those recurrence equations.

The aim of the lecture is to formulate recurrence equations to count various objects or scenarios. This approach leads to greater insight and simplifies the counting process. Once the equations are set up, the next goal will be to find solutions to these equations, laying the groundwork for deeper mathematical understanding.

Think of it like a recipe where you have to follow steps to create a dish. First, you gather the ingredients, which corresponds to setting up your equations. Once you have everything ready, you start cooking, which is akin to solving those equations to achieve your final dish.

So 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 substrings 00 is not allowed to appear in such a string and we want to find out how many such strings can be there.

The problem focuses on counting the number of binary strings of a certain length (n) that do not contain '00'. This sets a restriction on how we can form valid strings. To solve this, we introduce a function, say a(n), where a(n) denotes the number of valid n-bit strings without consecutive zeros.

Think of a digital lock code where you can use only two digits: 0 and 1. If you want to avoid typing two '0's in a row because they might cause the lock to jam, you're forced to carefully consider your options for each position of the code. This limitation helps shape the final outcome.

If we consider any n bit string which do not have 2 consecutive 0’s then there are only 2 possibilities for the starting bit of such a string. The starting bit of such a string could be 1 in that case the remaining n−1 length substrings should not have any occurrence of 2 consecutive 0’s.

To define our recurrence relation, we analyze the first bit of the string. If it starts with '1', the rest of the string (of length n-1) must adhere to the same rule of not containing '00'. If it starts with '0', the next bit must be '1' to avoid consecutive zeros, and the remaining possible string is of length n-2. Therefore, we can express the recurrence relation as: a(n) = a(n-1) + a(n-2).

Imagine constructing train tracks where two consecutive '0's indicate a missing section of the track. If the first section is intact (starting with '1'), there are still options to build further. However, if the first section is empty (starting with '0'), the next must be filled with a train (denoted by '1'). This sequential decision-making defines the rules for constructing valid arrangements.

However, the argument or the discussion that we had holds only if n ≥ 3. Because if I take n = 2, then this argument would not hold because we a(0) upon substitution.

The derived recurrence relation (a(n) = a(n-1) + a(n-2)) starts to hold significance when n is greater than or equal to 3. For base cases such as n=1 or n=2, we need to define initial conditions explicitly because our recurrence logic does not account for base strings of very short lengths. For example, a(1) has to equal 2 and a(2) has to equal 3.

Think of a game where rules change depending on the number of players. If there are only 1 or 2 players, the game mechanics don't kick in as they would with 3 or more players. Here, defining how the game works with just 1 or 2 players is essential before applying the broader rules.

So now we know how to count using recurrence equations. The next thing that we would like to do now is how to solve those recurrence equations.

After establishing the recurrence equations and initial conditions necessary for our counting problems, the next phase of learning will be focused on solving these equations. The solutions will provide closed-form formulas for counting objects satisfying specific conditions.

Concluding our recipe metaphor: after gathering ingredients and following steps, we look forward to finding out not just what we've cooked, but more importantly, how to replicate or improve upon it in future cooking adventures.

--