14. Solving Linear Homogenous Recurrence Equations – Part I

Hello everyone, welcome to this lecture on solving linear homogenous recurrence equations part 1.

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. Because, until and unless you do not have a closed-form formula you may not be able to come up with a solution. You have to solve the recurrence equation. So we already discussed the iterative method in the last lecture. In this lecture, we will continue our discussion on solving linear homogenous recurrence equations. And we will discuss one category, namely when we have non-repeated characteristic roots.

In this part, the lecturer introduces the topic of solving linear homogenous recurrence equations. It's important to understand that such equations can be used to solve counting problems, which means we can determine how many ways we can arrange or select items based on specific rules. The lecturer emphasizes that the process requires two main steps: first, creating the recurrence equation that models the problem, and second, finding a closed-form formula to represent the solution. Without the closed-form formula, it is difficult to express the solution clearly. Furthermore, the lecture indicates that they will focus specifically on the case where the roots of the characteristic equation are non-repeated, which is an important element in solving such equations.

Think of finding the number of ways to arrange books on a shelf as a counting problem. First, you need a rule or recipe (recurrence equation) that tells you how the arrangements depend on the previous arrangements. Once you have that rule, you can create a formula (closed-form solution) that helps you find the total arrangements instantly, without having to work through every possibility each time.

So just to quickly recap, what exactly are linear homogenous recurrence equations of degree 2? The general form is T(n) = aT(n-1) + bT(n-2). You have an infinite sequence where the n-th term of the sequence depends upon the previous 2 terms, i.e., T(n) is always dependent on T(n-1) and T(n-2). The recurrence equation for the Fibonacci sequence is an example of linear homogenous equation.

Here, the lecturer defines linear homogenous recurrence equations, specifically focusing on degree 2 equations. The format is given as T(n) = aT(n-1) + bT(n-2), where the current term (T(n)) is derived from the previous two terms. This explanation clarifies that the sequence is based on a finite number of prior terms, making it crucial to know the values of at least T(n-1) and T(n-2) to calculate T(n). An example provided is the Fibonacci sequence, which follows this kind of recurrence relationship, making it a practical example of how such equations work.

Consider a family tree where each generation depends on the previous ones. If you want to predict how many descendants will appear in a future generation (for example, your grandchildren), you might say: 'The number of grandchildren will depend on how many children I have and how many children each of my children has.' This shows how the current generation (grandchildren) relies on the previous two generations (your children and your grandchildren's parents).

I will first demonstrate the process assuming that we have a linear homogenous recurrence equation of degree 2. When I say degree 2 that means the n-th term of that infinite sequence is dependent on the previous two terms, namely, it depends on T(n-1) and T(n-2) where a ≠ 0. The characteristic equation will be in the form of x^2 - ax - b = 0. This quadratic equation will have 2 roots, called characteristic roots.

In this section, the lecturer introduces the concept of the characteristic equation tied to the homogenous recurrence equation. The degree of the equation reflects how many previous terms it depends on—in this case, two terms. The characteristic equation takes the form of a quadratic equation, which means it can have two roots that serve as the foundation for finding the general solution of the recurrence relation. The roots are considered 'characteristic roots' as they carry crucial information for the overall solution of the sequence.

Imagine you're creating a recipe that takes flavors from two previous dishes to create a new one. Here, the recipe (characteristic equation) combines aspects of the previous two dishes (characteristic roots). Just as a dish can turn out differently based on how you mix flavors or ingredients in the recipe, the sequence will vary based on the roots of the characteristic equation.

Now there could be 2 possibilities: the roots are distinct or they could be the same. When I say non-repeated I mean the former case where the roots are different. Once you have found the distinct characteristic roots, any sequence that satisfies the recurrence relation will have the n-th term of the form T(n) = α * r1^n + β * r2^n.

This part focuses on the two cases of the roots found in the characteristic equation. If the roots are distinct (meaning they are different), the solution of the recurrence relation can be expressed in a specific format involving constants α and β that multiply the roots raised to the power of n. This structured form gives a clear path to calculate any term in the sequence, as long as you know the roots and the constants. The underlying idea is that any sequence arising from the recurrence equation will have a predictable pattern once the roots are established.

Consider a plant's height growing over time based on its past heights. If you find that each growth period (day) relies distinctly on growth from the last two days (roots), you can predict its height in the future using a fixed method. This method (the equation form) allows you to neatly calculate its height for any given day, just as roots help break down the terms in the sequence.

If you are given the initial conditions, say T(0) = a and T(1) = b, you can use these values to determine α and β by substituting into your n-th term formula.

Here, the lecturer explains how to determine the constants α and β in the solution using initial conditions. Provided the values for T(0) and T(1), you can set up equations by substituting these into the general term expression. This allows you to calculate the specific values for these constants, thereby allowing you to not only express the sequence generally but also pinpoint exact terms based on the provided information.

Think of a bank account where you know your balance at two specific points in time (initial conditions). If you know how money grows over time based on a certain interest rate (the equation), you can use your known balances to backtrack and determine how much was added or compounded in those periods (the constants α and β). This way, you can clearly state the growth of your account for any other time in the future.

--