How do I solve this recurrence relation

Question

How do I solve the following recurrence relation:

T(n)=4T(n-1) - 3T(n-2)

I tried using substitution but failed as I was unable to find any "general" i-th term for it. Any help?

Edit: Sorry, I forgot to mention the base case:

T(0)=0
T(1)=2

Answer 1

The characteristic polynomial has roots $r=1$ and $r=3$ so the solution has to be something like $$T_n=1^n A+ 3^n B=A+ 3^n B$$ Using the conditions $$T_0=A+B=0$$ $$T_1=A+3B=2$$ gives two linear equations for $A$ and $B$; the solutions are $A=-1$, $B=1$. So, finally $$T_n=-1+3^n$$ If the value of $T_0$ and $T_1$ were not given, you would have obtained $$A=\frac{3{T_0}-{T_1}}{2} $$ $$B=\frac{{T_1}-{T_0}}{2}$$