How can I prove that $\log^*n = o(\log^{(k)}n)$ for all natural number $k$?

Question

I have to prove that $\log^*n = o(\log^{(k)}n)$ for all natural number $k$.

$\log^*n$ is iterated logarithm function

$\log^{(k)}n$ means : $\log(\log(\log(...\log(n)))..)$ - applying the $\log(\cdot)$-function $k$ times on $n$.

I tried to prove it according to the defintion. I took $n=$ $2^{2^{.^{.^2}}}$ $ \ - \ 2$ appears $k$ times and tried to substitute it in the inequality :

$\log^*n$ $\leq$ $c$ $\cdot$ $\log^{(k)}n$, but I did not get what I want. I think this is the right direction for the solution.

Answer 1

Hint: Using Knuth's up-arrow notation, let $a_n = 2 \uparrow \uparrow n$. We have $\log^{\ast}(a_n) = n$ while $\log^{(k)}(a_n) = 2\uparrow\uparrow (n-k)$. Then one should consider what happens if $n$ is sufficiently large.

Answer 2

An alternative way:

First note the following: There are integers $n$ such that both inequalities $\log^{(k)}(n) = 1$ and $\log^*(n) = k$ are simultaneously satisfied. So there are integers $n$ such that $\log^*(n)$ is $k$ times as large as $\log^{(k)}(n)$.

However, on the one hand, for $n$ such that the inequality $\log^{(k)}(n) \le 1$ is satisfied, note that the inequality $\log^*(n) \le k$ is also satisfied.

On the other hand: For $n$ such that $\log^{(k)}(n) \ge 1$, let us write $A(n)=\log^{(k)}(n)$. Then it is easy to check the following: $$\log^*(n) = k+\log^*(A(n)).$$
However, $A(n)$ is an increasing, unbounded function of $n$, so $\log^*(A(n)) \in o(A(n))$. Furthermore, $k$ is fixed so $k+\log^*(A(n))$ is $O(\log^*(A(n))$, which is $o(A(n))$. Thus:

$$\log^*(n) = k+\log^*(A(n))$$ $$= O(\log^*(A(n)) = o(A(n)) = o(\log^{(k)}(n)),$$ which is what you want.