13. Counting Using Recurrence Equations

Just to recap, in the last lecture we discussed about the rules of permutations and combinations used for counting. We also discussed about permutations with repetitions and combinations with repetitions. And we also discussed about combinatorial proofs. So in this lecture we will introduce a new counting technique which is extensively used in discrete mathematics and in computer science and this is basically counting using recurrence equations.

In this chunk, we introduce the main topic of the lecture, which is counting using recurrence equations. The speaker mentions that in earlier sessions, concepts like permutations and combinations were discussed. The aim of this lecture is to present a new technique that simplifies counting problems in discrete mathematics and computer science. Recurrence equations allow us to express the counts of sets or strings in terms of smaller subsets.

Imagine you have a large collection of toys, and you can organize them into different sets. Counting how many ways to arrange a small subset of those toys helps understand the larger collection better. Similarly, recurrence equations let us build up from simpler counting problems to solve more complex situations.

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: A(n)! = n * A(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.

This chunk explains what a recurrence equation is. A recurrence equation relates a term to one or more of its previous terms. An illustration is given with the factorial function, where the factorial of n is defined in terms of the factorial of n minus one. This property allows us to find the value of complicated expressions by breaking them down into simpler components.

Think of a staircase where each step represents a person's contribution to climbing the stairs. The last step (n) depends on how many people were already on the previous steps (n-1, n-2, etc.). Just as every climber depends on the ones before them, each term in a recurrence equation depends on earlier terms.

So imagine I want to find out the number of n bit strings that do not have an occurrence of 2 consecutive 0’s. And we want the general answer namely we want to find the number of such strings for any n. 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.

This chunk presents a specific counting problem: how many n-bit strings exist that do not contain two consecutive zeros. The function F(n) is defined to count these valid strings. This sets the stage for us to formulate a recurrence relation that counts valid strings based on string lengths.

Imagine constructing a fence using only two types of panels: solid panels (1) and transparent panels (0). If you prohibit using two transparent panels next to each other, you'll need to count the valid arrangements. Each arrangement builds up from smaller arrangements just as we derive F(n) from previous bit counts.

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 could be 1, in that case the remaining (n-1) length substring should not have any occurrence of 2 consecutive 0’s. The second possibility could be that the string starts with 0. If the string starts with 0 and if we want that overall string should not have any occurrence of 2 consecutive 0’s, then definitely the second position of that string should be 1.

In this chunk, the examples illustrate how we build the recurrence relation. If a valid string starts with '1', then the rest of the string (length n-1) must also be valid. If it starts with '0', the next bit must be '1', leaving a valid string of length (n-2). This leads us to the relation F(n) = F(n-1) + F(n-2).

Consider making a sandwich with rules: if you start with a slice of bread, you must continue building with certain fillings. However, if you start with a lettuce wrap (0), the next item must be a protein (1). Each starting choice leads you to unique combinations just like our recurrence relationship.

However, the argument that we had holds only if n ≥ 3. So now you might be wondering what about the output of the F function on inputs which are less than 3. So we will be giving some initial conditions. These are called initial conditions because the recursive functions are not applicable for the case when n = 1 and n = 2.

Here, the chunk emphasizes the importance of initial conditions for the recurrence relation. When n is less than 3, we cannot use the recurrence formula directly because fewer bits don’t provide enough information. For example, we conclude F(1) = 2 and F(2) = 3, defining the starting points for our recursion.

Think of a game that requires a minimum number of players to begin. If there aren’t enough players (less than 3), you can't play the game. Similarly, in our recurrence function, you need these specific base cases (F(1) and F(2)) to start building further values.

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? And when I say I want to solve a recurrence equation I mean finding a closed-form formula for that recurrence equation.

In this final chunk, the focus shifts to solving the recurrence relation we’ve established. The speaker indicates the goal to express F(n) as a closed-form function rather than recursively calculating each value. This simplification allows for quicker calculations and better understanding.

Imagine being able to predict the weather using a formula rather than checking daily reports. Just as such a formula can help swiftly generate meaningful forecasts, solving recurrence equations provides a powerful way to calculate values without tedious computation.

--