3
$\begingroup$

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.

  • 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$`2012-03-07

2 Answers 2

3

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

1

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.