13.5. Solving Recurrence Equations

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: T(n)! = n * T(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. Similarly we are familiar with the famous Fibonacci function where we know that F(n) = F(n-1) + F(n-2). So again this is an example of recurrence equation. 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.

Recurrence equations are mathematical equations that define sequences recursively. Instead of providing a formula for the nth term directly, they express it in terms of previous terms. For example, the factorial function and Fibonacci sequence both illustrate this concept. In the factorial equation T(n) = n * T(n-1), the value for n is determined by its relation to the factorial of n-1. This recursive approach allows us to simplify complex counting problems in mathematics and computer science.

Think of a family tree where each generation is defined by the previous one. Just as the size of a family at a certain generation can be determined by the sizes of the previous generations, recurrence equations help us derive values from previously known values.

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. We say that let S(n) be a function which on input n gives you the number of n bit strings which do not have two consecutive 0’s.

In this example, we are trying to determine the number of valid string combinations of n bits, where two consecutive zeros ('00') are not allowed. By defining S(n) as the function that counts these strings, we can focus on how to derive the count for larger n based on smaller values of n, which will eventually lead to a recurrence relationship.

Imagine you are creating a password with certain restrictions. If you can only use '1' and '0' and you cannot use '00' consecutively, the valid combinations for a 3-character password need to be counted. This restriction helps illustrate how certain counting methods, like the recurrence equation, can be applied.

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 of such a string. The starting bit of such a string 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 of length n starts with 0. If the string starts with 0, definitely the second position of that string should be 1, because if the second position is 0, the property is violated. So the recurrence is then S(n) = S(n-1) + S(n-2).

The logic here involves breaking down the problem of counting valid strings based on their starting characters. If a string starts with '1', the remaining portion (n-1) must also be valid. If it starts with '0', the next character must be '1', and the remaining portion is then (n-2). This breakdown leads to the recursive formula S(n) = S(n-1) + S(n-2) which describes how the count of valid strings relates to smaller strings.

Imagine you're designing a seating arrangement with certain rules. If you choose a seat (representing '1'), you can fill the remaining seats (counting down to n-1). If you choose to start with a blank seat (representing '0'), you must fill the next position with a specific choice (like '1'), and this approach continues for the remaining seats.

However, the argument holds only if n ≥ 3. Because if I take n = 2, then the possible strings of length 2 which do not have occurrences of 2 consecutive 0’s are 11, 10, and 01. Hence, S(2) = 3. But for any n ≥ 3, I can find the value of S for that particular n using the recurrence equation established earlier.

Base cases are necessary to kickstart the recursion. In this case, we've established that for n=1 and n=2, the counts are straightforward (S(1) = 2, S(2) = 3). These base values are what we utilize when calculating larger strings and ensure that our recurrence works smoothly as we build upon them.

Think of building blocks; if you know how many blocks can form the first two levels (S(1) and S(2)), you can easily determine how many combinations can form the third level (S(3)) using these previous 'foundations'.

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

Having established how to count certain objects using recurrence relations, the next step involves solving these relations. This means we want to express the count (like S(n)) not just in terms of itself and previous counts, but as a straightforward formula that allows us to compute values directly without iterating through all previous terms.

Returning to our previous examples, if you find a formula for your seating arrangement count rather than counting every possible valid arrangement individually, it not only saves time but also allows you to quickly evaluate any size you are interested in.

--