# Solving Recurrence Relation Question

How do i solve recurrence relations like $a(n) = 3a(n/2) - 2a(n/4); a(1)=3; a(2)=5$? I don't think I can draw a recursion tree since there's no function like $2n$ at the end.

• It appears this very same recurrence was asked before at this MSE link. – Marko Riedel May 14 '14 at 20:49

Let $b(m)=a(2^m)$ for $m=0,1,\ldots$. Then, your recursion relation becomes $b(m)=3 b(m-1)-2 b(m-2)$ with $b(0)=3$ and $b(1)=5$. This can be solved by introducing the generating function $f(q)=\sum_{m=0} b(m) q^m$ and determining it using the given recursion relation.
• Using the definition of $b(m)$, we see that $b(0)=a(2^0)=a(1)$ and similarly, $b(1)=a(2)$. – suresh May 14 '14 at 2:24