Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

As I know for solving recurrence relation like this $$a(n) = Aa(n-1)+B a(n-2)$$

we are trying to solve quadratic equation like this $$s^2-A \cdot s-B=0$$

Consider three cases

  1. Two distinct real roots, $s_1$ and $s_2$,then $$a(n)=a \cdot s_1^n+b \cdot s_2^n$$
  2. Exactly one real root
    $$a(n)=a \cdot s^n+b \cdot n \cdot s^n$$
  3. In case of complex roots,we use the sine and cosine functions Let us consider this situation $$a(n)=5 \cdot a(n-1)-6 \cdot a(n-2)$$ with $a(0)=1$ and $a(1)=4$

We have $s^2-5 \cdot s+6=0$ so $s_1=3$ and $s_2=2$. If put this information into the equation which considers two real roots and use the initial values, I get $$a(n)=2 \cdot 3^n-2^n$$

Am I correct? I have started solving such equations a few days ago and want to understand it well. Thanks.

share|improve this question
    
Can you please add some formatting to your post to make it more readable? For example: paragraphs, capitalization of first letter of each sentence etc. –  user2468 Mar 7 '12 at 19:31
1  
@dato Please, make your answers readable. I edited it, but it was way too much. To write expression like $a(n)=2\cdot3^n-2^n$, you start and end with $, don't put them in the middle:$a(n)=2\cdot3^n-2^n$ –  Pedro Tamaroff Mar 7 '12 at 20:09

2 Answers 2

up vote 3 down vote accepted

Well, it is easy to check if you got the right answer:

$$a_0=2*3^0-2^0 =1 \checkmark \,,$$ $$a_1=2*3^1-2^1 =4 \checkmark \,,$$ $$5a_{n-1}-6a_{n-2}=5*(2*3^{n-1}-2^{n-1})-6*(2*3^{n-2}-2^{n-2})$$ $$=3^{n-2}(30-12)-2^{n-2}(10-6)=2*3^n-2^n=a_n \checkmark \,.$$

share|improve this answer

There are various ways of addressing the kind of problem you have suggested here. In Hardy's Pure Mathematics p392-393 of my (tenth) edition, Miscellaneous Examples on Chapter VIII problems 15 and 16, there is a brief and beautiful exposition of how to use generating functions and partial fractions to find the solution of such problems, which justifies the general form of test function and test solution.

I would not automatically go for sine and cosine functions as the most convenient form of solution in the complex case.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.