15. Solving Linear Homogeneous Recurrence Equations – Part II

In the last lecture, we discussed how to solve linear homogeneous recurrence equations for the case when the characteristic roots were all distinct. A linear homogeneous recurrence equation of degree k has a characteristic equation of degree k. We find the characteristic roots, which can be real/complex and distinct/repeated. If all k roots are different, any sequence satisfying the recurrence condition is of the form: $a_n = \alpha_1 r_1^n + \alpha_2 r_2^n + \cdots + \alpha_k r_k^n$

In the previous lecture, the focus was on how to handle linear homogeneous recurrence equations when their roots are distinct. A linear homogeneous recurrence equation can be expressed in the form where we derive a characteristic polynomial from the recurrence relation. By finding its roots, we establish that each root contributes to a solution of the form that sums each root raised to the power n, multiplied by a constant. The constants can be adjusted to fit any specific initial conditions if provided.

Think of a recipe where, depending on the ingredients (the roots), you can create different dishes (sequences) by mixing them in various proportions (constants). If the ingredients are all different, you get a unique flavor every time you mix them together.

Now we will discuss the case when the characteristic roots are repeated. The general form of the recurrence equation is of degree 2. If the roots r1 and r2 are the same, then the theorem for distinct roots no longer holds. If you recall, when roots are distinct, the solution takes a simpler form. In the case of a repeated root, the solution becomes: $a_n = (\alpha_1 + \alpha_2 n) r^n$

In the case where the roots are repeated, the form of the solution must change because the algebraic properties of roots can result in a loss of uniqueness in the constant factors. With repeated roots, each unique solution must include a polynomial term that accounts for the multiplicity of the root. This means that once we derive a general solution based on the repeated roots, it takes into account not just the powers of the root but also multiplicative factors that increase linearly with n.

Consider a situation where you're making a smoothie, and your main ingredient, bananas, are all the same ripeness (the repeated root). You can still vary the flavor by adding other ingredients, but because the bananas are the same, you might need to blend them differently to get a desirable smoothie. The addition of something like protein powder (the linear term in n) helps enhance the texture of your smoothie, making it richer.

For degree 2 characteristic equations where roots are identical, we denote the common root as $r$. The general form of any sequence satisfying the recurrence condition becomes: $a_n = (\alpha_1 + n \alpha_2) r^n$. To satisfy initial conditions, you substitute the specific values to determine the constants.

When you have a degree 2 characteristic equation with repeated roots, the general solution acknowledges the multiplicity of the roots through its polynomial term and adjusts the format accordingly. By substituting initial conditions into this general solution, it allows us to compute exact constants that will yield a specific sequence instead of merely providing a general solution.

Imagine you're playing a game where there's a repeating score you need to match to achieve a high score (the common root). Each time you play (each n), the essence remains the same, but you can adjust your strategy (the constants) to obtain that score consistently and even enhance it as you progress.

Once initial conditions are provided, substituting values allows you to form equations in $\alpha_1$ and $\alpha_2$. Solving these equations gives you exact constants leading to the specific sequence that satisfies both the recurrence relation and the initial conditions.

Finding exact constants is crucial in modeling specific situations or problems using recurrence relations. By plugging in the values of n that correspond to the initial conditions into our general form, we create a system of equations which, upon solving, yields unique values for our constants. This step is necessary for obtaining the explicit terms of the sequence you're analyzing.

It’s like crafting a custom outfit where you measure the dimensions of a fitting (initial conditions) to calculate how much fabric (the constants) you need to create a perfect dress (the specific sequence). Without the measurements, you could only guess, but with them, you can achieve a perfect fit.

--