Bound summation of successive square roots

Question

What is a tight upper bound for $f(n)$ where $f(n) = f(\sqrt{n}) + \frac{1}{n}$. One can easily find the following upper bound $O(\lg \lg n)$, however I'm interested in a tight bound.

Regards.

Answer 1

I'll assume that $f$ is defined on the integers and that your recurrence is really

$$ f(n) = f(\lfloor \sqrt{n} \rfloor) + \frac{1}{n}. $$

For a given $n \in \mathbb N$ let $m = \lfloor \lg \lg n \rfloor$, where $\lg = \log_2$. It follows that

$$ 2^{2^m} \leq n < 2^{2^{m+1}}. \tag{1} $$

Define the integers $\{s_k\}_{k=0}^{m+1}$ by $s_{m+1} = n$ and

$$ s_k = \left\lfloor \sqrt{s_{k+1}} \right\rfloor, \qquad k=0,1,\ldots,m. $$

From $(1)$ we see that $s_0 = 1$ and

$$ s_k \geq 2^{2^{k-1}} $$

for all $k$, so upon unfolding the recurrence for $f$ we find that

$$ \begin{align} f(n) &= f(1) + \sum_{k=1}^{m+1} \frac{1}{s_k} \\ &\leq f(1) + \sum_{k=1}^{m+1} 2^{-2^{k-1}} \\ &< f(1) + \sum_{k=0}^{\infty} 2^{-2^k}. \end{align} $$

In particular, $f(n) = O(1)$.