4.3 – Non-Homogeneous Linear Recurrence Relations

Consider the following non-homogeneous linear recurrence relation:

a_n = { a_n-1 + a_n-2 } + { 3ⁿ + n3ⁿ + n² + n + 3 }
                 (1)                               (2)

Part (1) is the homogeneous part of the recurrence relation, which we now call it as the associated linear homogeneous recurrence relation. Part (2) is of our interest in this section, it is the non-homogeneous part. Solving this kind of questions are simple, you just need to solve the associated recurrence relation (just like how you did in the previous section), then solve the non-homogeneous part to find its particular solution. These two sections are solved separately, which we will combine the results together in the end.

---

Example 1 (terms of the form kⁿ):

a_n = 3a_n-1 + 2ⁿ

We first proceed to solve the associated linear recurrence relation (a.l.r.r.), which is
a_n = 3a_n-1
The characteristic equation gives us r = 3, and therefore
a_n = c₁(3ⁿ)

Now that the associated part is solved, we proceed to solve the non-homogeneous part. Using a smart guess, we let
a_n = c₂2ⁿ

From here, we then deduce that a_n-1 = c₂2^n-1. Putting these 2 equations back to the initial recurrence relation a_n = 3a_n-1 + 2ⁿ, we have
c₂2ⁿ= 3c₂2^n-1 + 2ⁿ
(c₂ – 1)2ⁿ= 3c₂2^n-1
2(c₂ – 1)= 3c₂
2(c₂ – 1)= 3c₂

And so we have c₂ = –2, which then gives us a_n = –2(2ⁿ) = –2ⁿ⁺¹. Combining both the answers for the associated and non-homogeneous part, we have our general solution
a_n = c₁(3ⁿ) – 2ⁿ⁺¹

If we were given the initial condition a₀ = 2, then our particular solution will be
a_n = 4(3ⁿ) – 2ⁿ⁺¹

This is the the general rule that we follow: For any amount of terms with the form kⁿ, we shall let a_n be kⁿ multiplied by a constant. So if the non-homogeneous part is a_n = 5ⁿ + 78ⁿ, then we let the answer be a_n = c₁5ⁿ + c₂78ⁿ, in which c₁ and c₂ are constants to be found. The same goes to the form nkⁿ, in which you let a_n = c₁nkⁿ. However, there is an exception, when the root r is of the same form as kⁿ. For example,

a_n = 2a_n-1 + 2ⁿ

You get r = 2, which you will get an a.l.r.r. of a_n = c₁2ⁿ, which has the same form with the non-homogeneous part! In this case, you need to multiply your non-homogeneous part with n. Which means, you let

a_n = nc₁2ⁿ and a_n-1 = (n – 1)c₁2^n-1

And using the same method, you put it back to the initial equation,
nc₁2ⁿ = 2(n – 1)c₁2^n-1 + 2ⁿ

and you find c₁ from here.

Similarly, if
a_n = 2a_n-1 + 3(2ⁿ) + 5n(2ⁿ)
you let your non-homogeneous part be
a_n = c₁n2ⁿ + c₂n²(2ⁿ)

and if
a_n = –4a_n-2 – 4a_n-2 + 3(2ⁿ) + 5n(2ⁿ)
which has a double root r = 2, then you will have a non-homogeneous part of
a_n = c₁n²(2ⁿ) + c₂n³(2ⁿ)

as long when the kⁿ or nkⁿ term is already found in the a.l.r.r. once, then multiply n to all the terms, and multiply n² if it is found twice. If you are curious why it is so, you could actually try without following this rule. You find that you can’t get the correct answer.

---

Example 2 (polynomial terms, n² + n + c or etc)

a_n = 3a_n-1 + n² + 5n + 3

It is the same for the a.l.r.r., a_n = c₁(3ⁿ). But for the non-homogeneous part, we let
a_n = c₂n² + c₃n + c₄                       (1)
a_n-1 = c₂(n – 1)² + c₃(n – 1) + c₄  (2)

I think you might have got the pattern by now.  Note that if the equation was
a_n = 3a_n-1 + n² + 3
a_n = 3a_n-1 + n² + 5n or
a_n = 3a_n-1 + n²
we still need to use the above, a_n = c₂n² + c₃n + c₄. This is because we need to account for the possibly missing terms which might arise in the particular solution.

So, just like example 1, substitute back both the equations (1) and (2) into the initial recurrence relations, then find c₂ to c₄, and combine with the a.l.r.r. to find c₁ with the given initial condition, say a₀ = 1. However, there is also an exception for this case, which is when one or two of the characteristic roots r = 1. For example,
a_n = 2a_n-1 – a_n-2 + n² + 5n + 3

You obtain a double root r = 1 for your a.l.r.r.. Since 1ⁿ = 1, then your a.l.r.r. will be of the form
a_n = c₁ + nc₂
which will clash with you equation for your non-homogeneous part if you use the same equation like the above, a_n = c₂n² + c₃n + c₄. Instead, you should use a_n = c₂n⁴ +n³ + c₄n², which is multiplied with n² to it. Similarly, if it were a first order recurrence relation with one root r = 1, then you multiply n, and if it were a third order recurrence relation with a triple root
r = 1, then you multiply n³ (notice the similarity with example 1). Again, you can try doing without following the rules, which will result in you not getting the required answer.

---

You need to do some practices on this section, as the recurrence relation questions in STPM are mainly from this section. Later on, when you do 2nd order differential equations, you will see that the solving methods of both sections are actually quite similar. ☺