closed form iterated logarithms

Question

Is there any way that we could bound the following sum by a closed form expression

$\sum_{i=1}^{\log^* N} \log^{(i)}N$ where $\log^{(i)}$ is the $\log$ function iterated $i$ time?

Thanks

Answer 1

Let $S(x)=\displaystyle\sum_{i=1}^{\log^* x} \log^{(i)}x$.

Then $S(x) \le (\log^* x)(\log x)$, because $\log x \le x$.

Empirically, it seems that $S(x) \sim C \log x$, with $C < 1.26$ for $x$ near $10^6$.

Nevertheless, one should not mistake $\log^* x$ for a constant, regardless of how slow it grows.

I'd like to know the value of $\displaystyle\lim_{x\to\infty} \dfrac{S(x)}{\log x}$ .

Answer 2

Let $\displaystyle S(x)=\sum_{i=1}^{\log^* x} \log^{(i)}(x)$. It's easy to show that $\log x\leq \frac{x^\alpha}{\alpha e}$ for $\alpha >0$. Pick $\alpha<1$ so that $c={\alpha e}>1$. Then $\log\log x\leq \frac{1}{c}(\log x)^\alpha$. Apply this to higher terms to get a convergent geometric series and obtain $$\lim_{x\to\infty} \frac{S(x)}{\log x}=1$$ Basically the terms decrease so fast that only the first term matters.