First and second derivative of a function log*(n) ("log star").

Question

I would like to ask what are the derivative values (first and second) of a function "log star": $f(n) = \log^*(n)$?

I want to calculate some limit and use the De'l Hospital property, so that's why I need the derivative of "log star": $$\lim_{n \to \infty}\frac{\log_{2}^*(n)}{\log_{2}(n)}$$

More about this function: https://en.wikipedia.org/wiki/Iterated_logarithm

Answer 1

You might try to use the definition of derivative to find your solutions $$ \lim_{\Delta x \rightarrow 0}\frac{f(x+\Delta x)-f(x)}{\Delta x} $$ and evaluate at the different intervals that are valid for the function.

Answer 2

Hint: take $n=2^m$ in your limit (and make sure you understand why you can do this!). Then (using $\lg(x)$ for $\log_2(x)$, which is a common convention) $\lg^*(n)=\lg^*(m)+1$, whereas $\lg(n)=m$. So your limit is $\lim\limits_{m\to\infty}\dfrac{\lg^*(m)+1}{m}$. But now we can take $m=2^r$, similarly, and get $\lim\limits_{r\to\infty}\dfrac{\lg^*(r)+2}{2^r}$. And since $\lg^*(n)\lt n$ for all $n\gt 1$ (this should be easy to prove) this gives you the limit you're after.