4.2 – Homogeneous Linear Recurrence Relations

Recall that you learnt in the previous section how to model a situation using recurrence relations. The equations are helpful, however, it doesn’t really help much if you are searching for a huge term. For example, the relation a_n = 2a_n-1, given the initial condition a₀ = 1, finding the term a₁₀₉ will be tiring, as it will take you forever to get there. When we say that we solve a recurrence relation, it means that we are trying to convert the relation into an equation in terms of n instead of a_n, which obviously, would be easier for you to calculate the nth term.

In this section, I’ll be showing you how to solve 2nd order homogeneous linear recurrence relations. The non-homogeneous part follows from here in the next section.

---

2 DISTINCT ROOTS

Given a recurrence relation a_n = 5a_n-1 – 6a_n-2, with initial conditions a₀ = 1, a₁ = 0. To start off with, we let a_n = rⁿ. This is a smart guess which we will find eventually that it is correct. We can then further deduce that a_n-1 = r^n-1, and a_n-2 = r^n-2. Substituting everything back into the equation, we have

rⁿ = 5r^n-1 – 6r^n-2

dividing the equation by r^n-2 (which is the smallest power), we get

r² = 5r – 6
r² – 5r + 6 = 0

which is a quadratic equation! This equation is called the characteristic equation, and r is called the characteristic root. Solving the equation, we get r = 2, 3. Again, using a smart guess, we deduce that the term a_n can be represented by the equation

a_n = c₁2ⁿ + c₂3ⁿ

So you noticed that the 2ⁿ and 3ⁿ must have came from the characteristic roots earlier on. This is the general solution of the recurrence relation. The terms c₁ and c₂ are just 2 constants, which we will find by using the initial conditions.

When a₀ = 1,
a₀ = c₁ + c₂ = 1    (1)

When a₁ = 0,
a₁ = 2c₁ + 3c₂ = 0
2c₁ = –3c₂            (2)

Now you have 2 simultaneous equations. Using the calculator, you can easily find that c₁ = 3, c₂ = –2. Substituting the constants back into the equation, you get

a_n = 3(2ⁿ) –2(3ⁿ)

which is what we called as the particular solution. This is the final answer that we are looking for. Now that you substitute n = 109, you can get the answer straight away for a_n! Now that you find the answer, try finding the first 5 or 6 terms, using both the recurrence relation a_n = 5a_n-1 – 6a_n-2 and the equation a_n = 3(2ⁿ) –2(3ⁿ). Do they contradict one another? Congratulations, you just learnt how to solve homogeneous recurrence relations!

---

2 EQUAL ROOTS

However, the above method is only true for 2 distinct roots in the characteristic equation. Take another example, a_n = –4a_n-1 – 4a_n-2, a₀ = 0, a₁ = 1. You get a characteristic equation r² + 4r + 4 = 0, r = –2. If you take the general solution as a_n = c₁(-2)ⁿ, then you are totally wrong. The correct answer should be a_n = c₁(-2)ⁿ + nc₂(-2)ⁿ. Notice the extra multiplied n in the second term. To summarize:

1. If the characteristic roots r₁ and r₂ are distinct, represent them as a_n = c₁r₁ⁿ + c₂r₂ⁿ.
2. If the characteristic roots r are equal, represent them as a_n = c₁rⁿ + nc₂r₂ⁿ.

Distinct roots could be either real or complex. The method for both is the same.

---

I will not discuss the methods to solve higher order recurrence relations here. However, the method is actually the same. Just represent a_n = rⁿ, and you will get linear, quartic or cubic equations, which you could eventually solve and get an answer for it. Simple? ☺