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:

  • $\begingroup$ What are the base cases, for example $T(0) = ?, T(1) = ?$ $\endgroup$ – taninamdar Sep 21 '14 at 6:35
  • $\begingroup$ en.wikipedia.org/wiki/Recurrence_relation#Solving $\endgroup$ – lab bhattacharjee Sep 21 '14 at 6:35
  • $\begingroup$ Do you know about how to solve recurrence relationsw via the characteristic polynomial? That provides a straight solution. $\endgroup$ – Semiclassical Sep 21 '14 at 6:35
  • 2
    $\begingroup$ Also, $$\frac{T(n)-T(n-1)}{T(n-1)-T(n-2)}=3$$ $\endgroup$ – lab bhattacharjee Sep 21 '14 at 6:36
  • $\begingroup$ 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$.) $\endgroup$ – Akiva Weinberger Sep 21 '14 at 6:37

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.