# solving recurrence relations

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.

• 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
• @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

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