Ytukyg

How can I find the exact-closed form solution of this recurrence?

$$f(n) = 4f(n/3) + log(n),$$
where n is a power of 3, $f(1)=3$

My answer:
$f(n) = 4f(n/3) + log(n)$$

$$= 4(4f(n/3^2) + log(n/3))+log(n)$$

$$=4^2f(n/3^2)+4log(n)-4log 3+log(n)$$

$$=4^3f(n/3^3)+4^2log(n)-4^2log(3^2)+4log(n)-4log 3+log(n)$$

Continuing in this manner suggest the sum:

(This is where I stopped because I could not figure out any sequences that could further simplify this equation.)

I already know that the answer is
$$f(n)=4^{log(n)/log 3}(3+(4/9)log3)-(4/9)(log 3)-(1/3)log(n)$$

So what I really want is how we can come up with this answer.

As I suggested in my comment, you can define $n=3^i$ and $f(3^i) = g(i)$ to obtain
$$
g(i) = 4 g(i-1) + log(3) i.
$$

This difference equation can be solved like an ODE separating the solution in a particular and a homogeneous solution:
$$
g(i) = g_p(i) + g_h(i)
$$

For the homogeneous part,
$$
g_h(i) = 4 g_h(i-1),
$$
whose solution is $g_h(i)=acdot 4^i$. Now, for the particular solution,
$$
g_p(i) + acdot 4^i = 4 (acdot 4^{i-1} + g_p(i-1)) + log(3) i,
$$
$$
g_p(i) = 4 g_p(i-1) + log(3) i.
$$
Assuming $g_p(i) = bi+c$,
$$
bi+c = 4 (bcdot(i-1)+c) + log(3) i,
$$
collecting the terms,
$$
i(log(3) +3b) + 3c -4b=0.
$$
Therefore, $b=-log(3)/3$ and $c=4b/3=-4log(3)/9$, and the solution is
$$
g(i) = acdot 4^i - frac{log(3)}{3} left(i+frac{4}{3} right).
$$
Applying the initial condition at $i=0$,
$$
a = g(0) + 4frac{log(3)}{9},
$$
leading to
$$
g(i) = left(g(0) + 4frac{log(3)}{9} right) 4^i - frac{log(3)}{3} left(i+frac{4}{3} right).
$$
Substituting this in the RHS of the original equation leads to
$$
4g(i-1)+log(3) i = 4 left[left(g(0) + 4frac{log(3)}{9} right) 4^{i-1} - frac{log(3)}{3} left(i-1+frac{4}{3} right) right] + log(3) i=
$$
$$
left(g(0) + 4frac{log(3)}{9} right) 4^{i} - frac{log(3)}{3} left(4i-3i-4+frac{16}{3} right)=
$$
$$
left(g(0) + 4frac{log(3)}{9} right) 4^{i} - frac{log(3)}{3} left(i+frac{4}{3} right)= g(i),
$$
therefore our solution is right. Substituting again to write the solution in original variables, using $i=log(n)/log(3)$,
$$
f(n) = left(f(1) + 4frac{log(3)}{9} right) 4^{log(n)/log(3)} - frac{log(3)}{3} left( frac{log(n)}{log(3)}+frac{4}{3} right),
$$
or, using $f(1)=3$,
$$
f(n) = left(3 + 4frac{log(3)}{9} right) cdot 4^{log(n)/log(3)} - frac{log(n)}{3}- frac{4 log(3)}{9}.
$$

EDIT: Although I evoked the concept of differential equations, it's not really necessary to understand them to solve this difference equation. See that the equation can be written as
$$
g(i) = k g(i-1) + f(i).
$$
The terms in RHS are very different in their nature: the first one is a function of $g$ itself; if we keep only this term, the equation is $g(i)=k g(i-1)$, which is the most simple case of difference equation. You can find its solution simply iterating, $g(1)=k g(0)$, $g(2)=k g(1)=k^2 g(0)$, and so on, then $g(i)=k^i g(0)$. If an equation (both a difference or a differential equation) has only terms involving the independent variable (in this case, $g$), the equation is called homogeneous. However, our equation is not homogeneous, due to the term $f(i)$. We can however use a trick to solve the non-homogeneous equation. Assume that the final solution is $g(i)=g_h(i)+g_p(i)$, in which $g_h$ is the solution of only the homogeneous part. Substituting in the equation,
$$
g_h(i)+g_p(i) = k[g_h(i-1)+g_p(i-1)] + f(i),
$$
or
$$
[g_h(i)-k g_h(i-1)] + [g_p(i) - k g_p(i-1)- f(i)]=0.
$$
We can separate this equation in two simpler equations. Equating the terms between the first pair of brackets to $0$, we have $g_h(i)=k g_h(i)$, whose solution is $g_h(i)=ak^i$, in which $a$ is a constant (we can't use the initial condition yet). The second equation that we need to solve is $g_p(i) = k g_p(i-1) + f(i)$, which is similar to the original equation, but we now need to solve only the particular part corresponding to the non-homogeneous equation. Depending on $f(i)$ we can use some guesses in the form of $g_p(i)$. If $f(i)$ is a polynomial on $i$, for example, we can guess that $g_p(i)$ is a polynomial of same order and discover its coefficients. In our case, $f(i)=log(3) i$, then we can guess $g_p(i)=b i+c$. Using this guess in the equation, we discover $b$ and $c$ and have, finally, the solution to the difference equation.

Set $a_n=f(3^n)$, then $a_{n+1}=4a_n+nln 3$. Put $A_n=4^{-n}a_n$ so that $A_{n+1}-A_n=4^{-n-1}(a_{n+1}-4a_n)=4^{-n-1}(nln 3)$ and $A_N-A_0=sum_{n=0}^{N-1} A_{n+1}-A_n =sum_{n=0}^{N-1} 4^{-n-1}(nln 3)$. Thus $a_N=4^N(a_0+sum_{n=0}^{N-1} 4^{-n-1}(nln 3))$.