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.

  • $\begingroup$ 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. $\endgroup$ – user2468 Mar 7 '12 at 19:31
  • 1
    $\begingroup$ @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$ $\endgroup$ – Pedro Tamaroff Mar 7 '12 at 20:09

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 \,.$$


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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