14.5. Characterization of Sequences

So just to quickly recap, in the last lecture we discussed how we can solve counting problems by formulating recurrence equations and we also started discussing about how to solve the recurrence equations. Because when you want to count certain number of things using recurrence equations then there are two parts. First thing is formulating the recurrence equation and the second thing will be finding the closed-form formula or the solution for the recurrence equation.

In the study of counting problems, we often encounter situations that we can model using recurrence equations. A recurrence equation expresses the relation between the terms of a sequence based on previous terms. For instance, saying F(n) = F(n-1) + F(n-2) indicates that the n-th term can be calculated based on the two preceding terms. To get to a usable solution, it’s vital first to establish a valid recurrence equation, and then we need to work towards finding a closed-form solution.

Think of a family tree in which each new generation depends on the previous ones—just as each term in the recurrence depends on the earlier terms. To understand the whole tree (or sequence), you need to know how it develops from earlier generations.

I will first demonstrate the process assuming that we have a linear homogeneous recurrence equation of degree 2. When I say degree 2 that means the n-th term of that infinite sequence depends upon the previous two terms, namely, it depends on F(n-1) and F(n-2) where c ≠ 0.

A linear homogeneous recurrence equation of degree 2 means that the next term in the sequence can be constructed from the two most recent previous terms. A classic example is the Fibonacci sequence where each number is the sum of the two preceding numbers. The importance of 'homogeneous' indicates that there aren’t any additional terms like constants, influencing the terms.

This is similar to a sports team where a player's performance next season relies heavily on the collective performance of the last two seasons they played together. To predict next season's performance accurately, you must analyze both previous seasons.

In this case, I am assuming that you are given the initial conditions. Say the initial conditions are F(0) = c0 and F(1) = c1. The first step here will be to construct what we call as characteristic equation and the characteristic equation will be an equation in an unknown λ.

To solve the recurrence relation, we derive what is known as the characteristic equation. For the degree 2 case, this equation will typically take the form λ² - bλ - a = 0, where a and b are parameters from the recurrence relation. This equation helps to find the roots (values of λ) that dictate the behavior of the sequence.

Imagine trying to find a pattern in a complex dance where each step could be influenced by the last two moves. The characteristic equation acts like a choreographer, giving you the rules to determine what steps follow next based on prior moves.

Now there could be 2 possibilities: the roots λ1 and λ2 are distinct or λ1 = λ2 and they could be the same. When I say non-repeated, I mean the former case where the roots λ1 and λ2 are different.

The roots of the characteristic equation give insight into the behavior of the sequence. If the roots are distinct, the general solution to the recurrence relation takes on a specific form: F(n) = α * λ1^n + β * λ2^n. If the roots were repeated, the form would change slightly, incorporating an extra factor to account for the multiplicity of the roots.

This is akin to having two different paths through a forest. If both paths diverge at a point (distinct roots), you can experience a unique adventure by taking one path over the other. However, if the paths converge back at the same spot (repeated roots), the adventures seem similar, and the journey has to include a reminder of going back to the fork in the road.

Now if you are in this case then we can prove that any sequence which is the solution of the recurrence equation that is given to you will be of the form F(n) = α * λ1^n + β * λ2^n for some arbitrary constants α and β.

In the case where we have distinct roots, the form of the solution to our recurrence equations clearly indicates how the n-th term is influenced by the two roots. α and β are constants that would typically be determined by initial conditions. Understanding this form allows us to explicitly construct the sequence once we know the roots Y.

Imagine the sequence like baking a cake, where each layer depends on specific ingredients (roots). The constants α and β are the precise amounts of flour and sugar you decide to use, shaping the taste and texture of your cake while ensuring it turns out delicious.

--