1
$\begingroup$

Solve the recurrence relation:

$f(n) = 4f(n/3)+5$ where $n=3^k, k=1,2,3...$ and $f(1)=5$

I never seen a recurrence relation like this before. What would I need to use or do to solve this?

$\endgroup$
  • 1
    $\begingroup$ You could, as usual, try induction. $\endgroup$ – Lucas Henrique Dec 10 '18 at 5:28
  • $\begingroup$ If you are only looking for an asymptotic bound, you can use master theorem. $\endgroup$ – platty Dec 10 '18 at 5:32
  • $\begingroup$ If $n=3^k$ then $n/3=3^{k-1}$ and it becomes a usual recurrence, provided know $f(1)$ and only want it for $f(3^k),$ $k \ge 0.$ $\endgroup$ – coffeemath Dec 10 '18 at 5:33
1
$\begingroup$

Let $f(3^k)=g(k)+c,k=0\implies?$

$5=g(k)-4g(k-1)+c-4c$

Set $c-4c=5$ so that $g(k)=4g(k-1)=4^rg(k-r)=4^kg(0)$

$\endgroup$
0
$\begingroup$

Also, you can find a tight result from the mater theorem and we can say $f(n) = \Theta(n^{\log_34})$, and as $n = 3^k$, $f(n) \sim (3^k)^{\log_34} = 4^k$.

$\endgroup$
0
$\begingroup$

One approach which I find useful is the following:

As already mentioned by Lucas Henrique, you can first of all define $a_k := f(3^k)$. This gives you the relation $$ a_k = 4a_{k-1} + 5, \quad \quad a_0 = 5 $$ From here on, you have several options. You can use generating functions, just plug in some values and try to find a pattern or assume you have a "big" $k$ and use the above formula several times: \begin{eqnarray} a_k &=& 4a_{k-1} +5\\ & = & 4 (4a_{k-2}+5)+5 = 4^2 a_{k-2} + (4+1)\cdot 5\\ & = & 4^2 (4a_{k-3} +5)+(4+1) \cdot5 = 4^3 a_{k-3} + (4^2 + 4 + 1)\cdot 5\\ & = & \dots \end{eqnarray} Now you may already derive a formula from that.

Hint: for $q \neq -1$, one has $\sum_{k=0}^n q^k = \frac{1-q^{n+1}}{1-q}$

$\endgroup$

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.