exact-closed form solution of recurrence

Question

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)+4\log(n)-4\log 3+\log(n)$$

$$=4^3f(n/3^3)+4^2\log(n)-4^2\log(3^2)+4\log(n)-4\log 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.

Answer 1

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)=a\cdot 4^i$. Now, for the particular solution, $$ g_p(i) + a\cdot 4^i = 4 (a\cdot 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 (b\cdot(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=-4\log(3)/9$, and the solution is $$ g(i) = a\cdot 4^i - \frac{\log(3)}{3} \left(i+\frac{4}{3} \right). $$ Applying the initial condition at $i=0$, $$ a = g(0) + 4\frac{\log(3)}{9}, $$ leading to $$ g(i) = \left(g(0) + 4\frac{\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) + 4\frac{\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) + 4\frac{\log(3)}{9} \right) 4^{i} - \frac{\log(3)}{3} \left(4i-3i-4+\frac{16}{3} \right)= $$ $$ \left(g(0) + 4\frac{\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) + 4\frac{\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 + 4\frac{\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.

Answer 2

Set $a_n=f(3^n)$, then $a_{n+1}=4a_n+n\ln 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}(n\ln 3)$ and $A_N-A_0=\sum_{n=0}^{N-1} A_{n+1}-A_n =\sum_{n=0}^{N-1} 4^{-n-1}(n\ln 3)$. Thus $a_N=4^N(a_0+\sum_{n=0}^{N-1} 4^{-n-1}(n\ln 3))$.