0
$\begingroup$

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.

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

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.

Look up how to solve two-term recursion relations with constant coefficients if you don't know how to do that else ask here.

$\endgroup$
  • $\begingroup$ thank you, why is it b(0)=3 and b(1)=5 when its a(1)=3;a(2)=5 $\endgroup$ – user2976568 May 14 '14 at 1:40
  • $\begingroup$ Using the definition of $b(m)$, we see that $b(0)=a(2^0)=a(1)$ and similarly, $b(1)=a(2)$. $\endgroup$ – suresh May 14 '14 at 2:24

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.