# Solve the recurrence relation $f(n) = 4f(n/3)+5$ where $n=3^k, k=1,2,3…$ and $f(1)=5$

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?

• You could, as usual, try induction. – Lucas Henrique Dec 10 '18 at 5:28
• If you are only looking for an asymptotic bound, you can use master theorem. – platty Dec 10 '18 at 5:32
• 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.$ – coffeemath Dec 10 '18 at 5:33

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

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

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