How can I prove that $\log^*n = o(\log^{(k)}n)$ for all natural number $k$? 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.
 A: 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.
A: 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.
