Consider the following **non-homogeneous linear recurrence relation**:

**a _{n} = { a_{n-1 }+ a_{n-2 }} + { 3^{n} + n3^{n} + n^{2} + 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 ^{n}):__

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

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_{1}(3^{n})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}2^{n}**

From here, we then deduce that **a _{n-1 }= c_{2}2^{n-1}**

**.**Putting these 2 equations back to the initial recurrence relation

**a**we have

_{n }= 3a_{n-1}+ 2^{n},**c**

_{2}2^{n}= 3c_{2}2^{n-1}+ 2^{n}**(c**

_{2}– 1)2^{n}= 3c_{2}2^{n-1}**2(c**

_{2}– 1)= 3c_{2}**2(c**

_{2}– 1)= 3c_{2}And so we have **c _{2} = –2, **which then gives us

**a**. Combining both the answers for the associated and non-homogeneous part, we have our

_{n }= –2(2^{n}) = –2^{n+1}**general solution**

**a**_{n }= c_{1}(3^{n}) – 2^{n+1}If we were given the initial condition **a _{0} = 2**, then our particular solution will be

**a**

_{n }= 4(3^{n}) – 2^{n+1}This is the the general rule that we follow: For any amount of terms with the form **k ^{n}**, we shall let

**a**

_{n }be

**k**multiplied by a constant. So if the non-homogeneous part is

^{n}**a**, then we let the answer be

_{n}= 5^{n}+ 78^{n}**a**, in which

_{n}= c_{1}5^{n}+ c_{2}78^{n}**c**and

_{1}**c**are constants to be found. The same goes to the form

_{2}**nk**, in which you let

^{n}**a**. However, there is an

_{n}= c_{1}nk^{n}**exception**, when the root

**r**is of the same form as

**k**. For example,

^{n}**a _{n }= 2a_{n-1} + 2^{n}**

You get **r = 2**, which you will get an a.l.r.r. of **a _{n }= c_{1}2^{n}, **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_{1}2^{n }**and

**a**

_{n-1 }= (n – 1)c_{1}2^{n-1}And using the same method, you put it back to the initial equation,**nc _{1}2^{n }= 2(n – 1)c_{1}2^{n-1} + 2**

^{n}

and you find **c _{1}** from here.

Similarly, if**a _{n }= 2a_{n-1} + 3(2^{n}) + 5n(2^{n})**you let your non-homogeneous part be

**a**

_{n }= c_{1}n2^{n}+ c_{2}n^{2}(2^{n})and if**a _{n }= –4a_{n-2} – 4a_{n-2 }+ 3(2^{n}) + 5n(2^{n})**which has a double root

**r = 2**, then you will have a non-homogeneous part of

**a**

_{n }= c_{1}n^{2}(2^{n}) + c_{2}n^{3}(2^{n})as long when the **k ^{n}** or

**n**term is already found in the a.l.r.r. once, then multiply n to all the terms, and multiply n

^{}k^{n}^{2}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__^{2 }__+ n + c or etc)__

**a _{n }= 3a_{n-1} + n^{2 }+ 5n + 3**

It is the same for the a.l.r.r., **a _{n }= c_{1}(3^{n}). **But for the non-homogeneous part, we let

**a**

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

_{n-1 }= c_{2}(n – 1)^{2 }+ c_{3}(n – 1) + c_{4 }(2)I think you might have got the pattern by now. Note that if the equation was**a _{n }= 3a_{n-1} + n^{2} + 3**

**a**or

_{n }= 3a_{n-1}+ n^{2 }+ 5n**a**

_{n }= 3a_{n-1}+ n^{2}we still need to use the above,

**a**

_{n }= c_{2}n^{2 }+ c_{3}n + c_{4}.

_{}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**_{2 }to **c _{4}**, and combine with the a.l.r.r. to find

**c**with the given initial condition, say

_{1}**a**. However, there is also an

_{0}= 1**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^{2 }+ 5n + 3You obtain a double root **r = 1** for your a.l.r.r.. Since **1 ^{n} = 1**, then your a.l.r.r. will be of the form

**a**

_{n }= c_{1}+ nc_{2}which will clash with you equation for your non-homogeneous part if you use the same equation like the above,

**a**

_{n }= c_{2}n^{2 }+ c_{3}n + c_{4}. Instead, you should use

**a**, which is multiplied with

_{n }= c_{2}n^{4}^{ }+n^{3}+ c_{4}n^{2}**n**to it. Similarly, if it were a first order recurrence relation with one root

^{2}**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

^{3}**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. ☺

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

ReplyDeletethankss..

ReplyDeletecan 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 .

ReplyDeleteThanks for sharing your notes! :) Very helpful!! :)

ReplyDeleteGood Job !! Thanks.

ReplyDeleteThanks 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...!!

ReplyDeletei got the concept to let me prepare for my semester exams ... thanks a lot

ReplyDeleteVERY NICE

ReplyDeleteCan u illustrate a ques having r(n)=constant

ReplyDeleteCan u illustrate a ques having r(n)=constant

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

ReplyDeleteexcellent, nicely explained, saved me lot of time

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

ReplyDeleteThanks!

ReplyDeleteAwesome dude, totally helpful

ReplyDelete