# How do I solve this recurrence relation

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

• What are the base cases, for example $T(0) = ?, T(1) = ?$ – taninamdar Sep 21 '14 at 6:35
• en.wikipedia.org/wiki/Recurrence_relation#Solving – lab bhattacharjee Sep 21 '14 at 6:35
• Do you know about how to solve recurrence relationsw via the characteristic polynomial? That provides a straight solution. – Semiclassical Sep 21 '14 at 6:35
• Also, $$\frac{T(n)-T(n-1)}{T(n-1)-T(n-2)}=3$$ – lab bhattacharjee Sep 21 '14 at 6:36
• Perhaps there's one or more number $\alpha$ such that $\alpha^n=4\alpha^{n-1}-3\alpha^{n-2}$? (If there are two such numbers, $\alpha$ and $\beta$, it's easy to see that $T(n)=A\alpha^n+B\beta^n$ solves the recurrence for all $A,B$.) – Akiva Weinberger Sep 21 '14 at 6:37

## 1 Answer

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}$$