0

Today I've learned the formal definition of the iterated logarithm.

$$ \log^*_b n:= \min\{i \in \mathbb N:\log^{(i)}_b n \leq 1\} \\ \log_b^{(1)} n := \log_b n \\ \log^{(i + 1)}_b n:= \log^{(i )}_b \log _b n \\ $$

Could somebody show me how to prove the alternative form

$$ \log^*_b n := \begin{cases} 0 & \mbox{if } n \le 1; \\ 1 + \log^*_b(\log_b n) & \mbox{if } n > 1 \end{cases} $$

using the formal definition above?

ACB
  • 3,713
Hawkeye332
  • 3

1 Answers1

0

(All $\log$s below have base $b$.)

Well, if $n\le 1$ then $\log^{(0)}n \le 1$, assuming $\log^{(0)}x=x$ (there is a case missing in your definition of $\log^{(i)}$), so that's the base case of the recursive definition.

For the inductive case, take any $n>1$ and we need to show that $\log^* n=1 + \log^*(\log n)$ using the $\min$ definition.

$\log^*n=k$ is the same as the statement $\log^{(k)}n\le 1\le \log^{(k-1)}n$ (the last part of the inequality following from $k$ being minimum such that $\log^{(k)}n\le 1$, and $k\ge 1$ because $n>1$).

We know that $\log^{(k)}n=\log^{(k-1)}(\log n)$.

We want to show that $1+\log^*(\log n)=k$ i.e. $\log^*(\log n)=k-1$. That's the same as saying that $\log^{(k-1)}(\log n)\le 1\le \log^{(k)}(\log n)$.

Can you finish the proof from here?

A.M.
  • 3,944
  • Yes, I can finish the proof (however, please correct any my mistakes). Since log* n = k, statement log* (log n) decrements k. Hence k - 1 = log^* (log n). – Hawkeye332 Feb 18 '22 at 19:28
  • @Hawkeye332 yes this is the thrust, but I'd frame it a bit more clearly in terms of $\min$. – A.M. Feb 18 '22 at 20:35