14.3. General Method for Solving Recurrence Equations

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 this chunk, we revisit what we learned about recurrence equations in the previous lecture. There are two major steps: 1) Formulate the recurrence equation which represents the counting problem, and 2) Find the closed-form solution that allows you to compute the terms of the sequence without iterating through all previous terms. This closed-form formula is essential for finding the solution efficiently.

Imagine you're assembling a puzzle. The pieces represent the values in a recurrence relation. First, you have to lay down a plan (formulate the equation) on how these pieces fit together (the recurrence). Once you have the plan, you can see the entire picture and assemble it without having to look at each individual piece sequentially (finding the closed-form solution).

So we are interested to come up with the general method for solving recurrence equations of this type. The general form is a_n = c_1 * a_(n-1) + c_2 * a_(n-2) + ... + c_k * a_(n-k), where a_n depends on the previous k terms.

In this chunk, we define the general form of a linear homogeneous recurrence equation of degree k. The n-th term (a_n) is calculated based on a linear combination of the previous k terms (a_(n-1), a_(n-2), ..., a_(n-k)). This recursion provides a method to build subsequent terms using a specified set of constants (c_1, c_2,...), with the stipulation that the leads coefficients are not zero.

Think of this equation as a recipe for a dish where the main ingredients are the last few dishes you made (the previous terms). Each dish (term) you're currently preparing depends on a specific combination of those last dishes (the constants determining how much of each previous term to use).

So the first step here will be to construct what we call a characteristic equation and the characteristic equation will be an equation in an unknown r. So r is an unknown variable. This characteristic equation will be a quadratic equation in r, typically formed as r^2 - c_1 * r - c_2 = 0 when considering a degree 2 recurrence.

To solve a linear homogeneous recurrence relation of degree 2, we start by constructing the characteristic equation. This quadratic equation helps us find the roots, which are crucial for determining the subsequent terms of the sequence. The form r^2 - c_1 * r - c_2 = 0 illustrates how we transition from the recurrence relation to an algebraic equation that can be solved using known root-finding methods.

Imagine setting up a path to a treasure (the solution). To find the way, you need landmarks (the quadratic equation) along the path. Each landmark indicates directions based on coordinates (the roots), guiding you as to where to go next, eventually leading to the treasure (the sequence values).

Now since this is a quadratic equation, we will have 2 roots for this equation, called r1 and r2, which can either be distinct or the same. In the case of distinct roots, the general solution of the recurrence relation can be expressed as a_n = α * r1^n + β * r2^n for some constants α and β.

In this section, we explore the implications of the roots of the characteristic equation. If the roots (r1, r2) are distinct, we can express the n-th term of the sequence as a linear combination of the roots raised to the power n, multiplied by constants α and β. This formula represents the general solution for sequences defined by distinct roots, showcasing how changes in these roots impact the behavior of the sequence.

Think of the roots as two different paths you can take to reach a destination. Depending on which path you take (which roots you use), you will end up in different places (different sequences). The final result (the n-th term) will be influenced by how much you weigh each path (the constants α and β).

If initial conditions are given, for example, a_0 = c_0 and a_1 = c_1, then you can solve for the constants α and β by substituting these values into your general solution.

Once the general form of the sequence is known, you can compute specific sequences if you have initial conditions. By substituting these initial values into the general equation, you can solve for the constants (α and β), making the formula not just general but specific to the initial conditions provided.

Returning to our earlier analogy of the treasure map, the initial conditions are like the starting coordinates you have. They help you pinpoint exactly what direction to start in as you follow the paths laid out by your landmarks. This sets you on the correct route towards the treasure, ensuring you don’t just wander blindly.

--