Wednesday, June 15, 2011

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 an = 2an-1, given the initial condition a0 = 1, finding the term a109 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 an, 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 an = 5an-1 – 6an-2, with initial conditions a0 = 1, a1 = 0. To start off with, we let an = rn. This is a smart guess which we will find eventually that it is correct. We can then further deduce that an-1 = rn-1, and an-2 = rn-2. Substituting everything back into the equation, we have

rn = 5rn-1 – 6rn-2

dividing the equation by rn-2 (which is the smallest power), we get

r2 = 5r – 6
r2 – 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 an can be represented by the equation

an = c12n + c23n

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

When a0 = 1,
a0 = c1 + c2 = 1    (1)

When a1 = 0,
a1 = 2c1 + 3c2 = 0
2c1 = –3c2            (2)

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

an = 3(2n) –2(3n)

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 an! Now that you find the answer, try finding the first 5 or 6 terms, using both the recurrence relation an = 5an-1 – 6an-2 and the equation an = 3(2n) –2(3n). 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, an = –4an-1 – 4an-2, a0 = 0, a1 = 1. You get a characteristic equation r2 + 4r + 4 = 0, r = –2. If you take the general solution as an = c1(-2)n, then you are totally wrong. The correct answer should be an = c1(-2)n + nc2(-2)n. Notice the extra multiplied n in the second term. To summarize:

1. If the characteristic roots r1 and r2 are distinct, represent them as
an = c1r1n + c2r2n.
2. If the characteristic roots r are equal, represent them as an = c1rn + nc2r2n.

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 an = rn, and you will get linear, quartic or cubic equations, which you could eventually solve and get an answer for it. Simple?

3 comments:

  1. Thanks for sharing your notes! :) I understood! :)

    ReplyDelete
  2. Can you help me getting more examples for me....I wanna practice

    ReplyDelete
  3. Where is generating function method and back tracking method to solve the recurrence relations

    ReplyDelete