Pages

Wednesday, June 15, 2011

4.3 – Non-Homogeneous Linear Recurrence Relations

Consider the following non-homogeneous linear recurrence relation:

an = { an-1 + an-2 } + { 3n + n3n + n2 + 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 kn):

an = 3an-1 + 2n

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

Now that the associated part is solved, we proceed to solve the non-homogeneous part. Using a smart guess, we let
an = c22n

From here, we then deduce that an-1 = c22n-1. Putting these 2 equations back to the initial recurrence relation an = 3an-1 + 2n, we have
c22n= 3c22n-1 + 2n
(c2 – 1)2n= 3c22n-1
2(c2 – 1)= 3c2
2(c2 – 1)= 3c2

And so we have c2 = –2, which then gives us an = –2(2n) = –2n+1. Combining both the answers for the associated and non-homogeneous part, we have our general solution
an = c1(3n) – 2n+1

If we were given the initial condition a0 = 2, then our particular solution will be
an = 4(3n) – 2n+1

This is the the general rule that we follow: For any amount of terms with the form kn, we shall let an be kn multiplied by a constant. So if the non-homogeneous part is an = 5n + 78n, then we let the answer be an = c15n + c278n, in which c1 and c2 are constants to be found. The same goes to the form nkn, in which you let an = c1nkn. However, there is an exception, when the root r is of the same form as kn. For example,

an = 2an-1 + 2n

You get r = 2, which you will get an a.l.r.r. of an = c12n, 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

an = nc12n and an-1 = (n – 1)c12n-1

And using the same method, you put it back to the initial equation,
nc12n = 2(n – 1)c12n-1 + 2n

and you find c1 from here.

Similarly, if
an = 2an-1 + 3(2n) + 5n(2n)
you let your non-homogeneous part be
an = c1n2n + c2n2(2n)

and if
an = –4an-2 – 4an-2 + 3(2n) + 5n(2n)
which has a double root r = 2, then you will have a non-homogeneous part of
an = c1n2(2n) + c2n3(2n)

as long when the kn or nkn term is already found in the a.l.r.r. once, then multiply n to all the terms, and multiply n2 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, n2 + n + c or etc)

an = 3an-1 + n2 + 5n + 3

It is the same for the a.l.r.r., an = c1(3n). But for the non-homogeneous part, we let
an = c2n2 + c3n + c4                       (1)
an-1 = c2(n – 1)2 + c3(n – 1) + c(2)

I think you might have got the pattern by now.  Note that if the equation was
an = 3an-1 + n2 + 3
an = 3an-1 + n2 + 5n or
an = 3an-1 + n2

we still need to use the above, an = c2n2 + c3n + c4. 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 c2 to c4, and combine with the a.l.r.r. to find c1 with the given initial condition, say a0 = 1. However, there is also an exception for this case, which is when one or two of the characteristic roots r = 1. For example,
an = 2an-1 – an-2 + n2 + 5n + 3

You obtain a double root r = 1 for your a.l.r.r.. Since 1n = 1, then your a.l.r.r. will be of the form
an = c1 + nc2
which will clash with you equation for your non-homogeneous part if you use the same equation like the above,
an = c2n2 + c3n + c4. Instead, you should use an = c2n4 +n3 + c4n2, which is multiplied with n2 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 n3 (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.

21 comments:

  1. This post was more helpful to me than anything else I could find. Thank you so much.

    ReplyDelete
  2. can u help me with finding the values of c2 to c4 for example 2? its only one equation that we get which contains c2,c3 and c4 .

    ReplyDelete
  3. Thanks for sharing your notes! :) Very helpful!! :)

    ReplyDelete
  4. Thanks for your notes..!! However I have one question, Is this procedure valid for the vector recurrences (i.e. a_n, a_n-1, a_n-2,.....all are vectors)?? Thanks...!!

    ReplyDelete
  5. Can u illustrate a ques having r(n)=constant

    ReplyDelete
    Replies
    1. Hi sorry but I seldom come back to this blog nowadays. I hope you found your answer somewhere! :)

      Delete
  6. Thanks it was really easy to understand the concept from here...Thanks a lot

    ReplyDelete
  7. excellent, nicely explained, saved me lot of time

    ReplyDelete
  8. if a(n+2)-6a(n+1)+9a(n)=3*2^n+7*3^n then what would be the particular equation?

    ReplyDelete
    Replies
    1. Hi sorry for the late reply... I hope you found your solution by now! :)

      Delete
  9. Thank you for sharing, This post was very helpful. :)

    ReplyDelete
  10. Thank you very much.This has really helped me a lot.

    ReplyDelete
  11. This content is very much helpful to me. Thanks a lot.

    ReplyDelete
  12. Great content and examples. Very relevant and specific to the required information

    ReplyDelete
  13. What motivates us to do the substitution $a_n=r^n$ ? Isn't there a more natural approach to solving recurrence relations? This method almost feels like an algorithm. It does not motivates any creativity. Help

    ReplyDelete