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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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