# Recurrence Relations for $c_1$ and $c_2$

For the following recurrence relation: $a_n = 3a_{n-1}+4a_{n-2}$, where $a_0=3$ and $a_1=2$ I solved it using quadratic equation by $x^2+3x-4$. So I got to $a_n = 4^nc_1 + c_2(-1)^n$. Now to find $c_1$ and $c_2$, my book says that $c_1 =1$ and $c_2=2$. I am so confused as to where that answers came from. I know that $$a_0=3=c_1+c_2$$ and $$a_1=2=4c_1-c_2$$ but cant see the solution for $c_1$ and $c_2$.

-
add to get $5c_1=5\iff c_1=1, c_2=3-c_1=3-1$ – lab bhattacharjee Apr 14 '13 at 15:57
So where did you get 5 from? – hjg hjg Apr 14 '13 at 16:07
$(c_1+c_2)+(4c_1-c_2)=3+2$ – lab bhattacharjee Apr 14 '13 at 16:09

You assume that there is a solution $a_n=cr^n$ and substitute that into your recurrence. This gives $cr^n=3cr^{n-1}+4cr^{n-2}$ which simplifies to $r^2-3r-4=0$ (Note the sign difference from what you have). This is solved by $r=4,-1$. Our solution is then $a_n=c_14^n+c_2(-1)^n$. Substituting in we get $3=c_1+c_2, 2=4c_1-c_2, 5=5c_1,c_1=1,c_2=2$. the final solution is then $a_n=4^n+2(-1)^n$

-
is this assumption always work for this kind of equation ? – chenbai Apr 15 '13 at 3:56
@chenbai: yes, unless you have repeated roots for the polynomial. Then you will get solutions of the form $n^mr^n$ where $r$ is the repeated root and $m$ ranges from $0$ up to one less than the root multiplicity. – Ross Millikan Apr 15 '13 at 3:59
thanks a lot! a very good method! – chenbai Apr 15 '13 at 4:27

Your equations for $c_1$ and $c_2$ are correct, so just solve them:

$$c_2=a_0 - c_1 \Rightarrow 4c_1-c_2 = 5c_1 - a_0 = a_1 \Rightarrow c_1 = \frac{a_0+a_1}{5}=1, \quad c_2 = 3-1 = 2$$

By the way, your characteristic polynomial should be $x^2 - 3x - 4$, but I guess it was a typo in your question.

-