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**, finding the term

_{0}= 1**a**will be tiring, as it will take you forever to get there. When we say that we

_{109}**solve**a recurrence relation, it means that we are trying to convert the relation into an equation in terms of

**n**instead of

**a**, which obviously, would be easier for you to calculate the

_{n}**n**th 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**To start off with, we let

_{0}= 1, a_{1}= 0.**a**. This is a smart guess which we will find eventually that it is correct. We can then further deduce that

_{n}= r^{n}**a**

_{n-1}= r^{n-1}_{}, and

**a**. Substituting everything back into the equation, we have

_{n-2}= r^{n-2}**r**

^{n}= 5r^{n-1}– 6r^{n-2}dividing the equation by **r ^{n-2 }**(which is the smallest power), we get

**r ^{2} = 5r – 6r_{}^{2} – 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**can be represented by the equation

_{n}**a _{n} = c_{1}2^{n} + c_{2}3^{n}**

So you noticed that the **2 ^{n}** and

**3**must have came from the characteristic roots earlier on. This is the

^{n}**general solution**of the recurrence relation. The terms

**c**and

_{1}**c**are just 2 constants, which we will find by using the initial conditions.

_{2}When

**a**,

_{0}= 1**a**

_{0}= c_{1}+ c_{2}= 1 (1)When **a _{1 }= 0**,

**a**

2c

_{1}= 2c_{1}+ 3c_{2 }= 02c

_{1 }= –3c_{2}(2)Now you have 2 simultaneous equations. Using the calculator, you can easily find that **c _{1} = 3, c_{2} = –2**. Substituting the constants back into the equation, you get

**a _{n} = 3(2^{n}) –2(3^{n})**

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**and the equation

_{n}= 5a_{n-1}– 6a_{n-2}**a**. Do they contradict one another? Congratulations, you just learnt how to solve homogeneous recurrence relations!

_{n}= 3(2^{n}) –2(3^{n})

__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} = 0, a_{1} = 1.** You get a characteristic equation

**r**. If you take the general solution as

^{2 }+ 4r + 4 = 0, r = –2**a**, then you are totally wrong. The correct answer should be

_{n}= c_{1}(-2)^{n}**a**Notice the extra multiplied

_{n}= c_{1}(-2)^{n}+ nc^{}_{2}(-2)^{n}.**n**in the second term. To summarize:

1. If the characteristic roots

**r**and

_{1}**r**are

_{2 }**distinct**, represent them as

**a**

2. If the characteristic roots

_{n }= c_{1}r_{1}^{n}+ c^{}_{2}r_{2}^{n}.**r**are

**equal**, represent them as

**a**

_{n }= c_{1}r^{n}+ nc^{}_{2}r_{2}^{n}.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^{n}**, and you will get linear, quartic or cubic equations, which you could eventually solve and get an answer for it. Simple? ☺

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

ReplyDeleteCan you help me getting more examples for me....I wanna practice

ReplyDeleteWhere is generating function method and back tracking method to solve the recurrence relations

ReplyDelete