Nested radicals with logarithms

191 Views Asked by At

The Wikipedia page about Nested radicals lists the following formula:

$$ \sqrt{n+\sqrt{n+\sqrt{n+\sqrt{n+\cdots}}}} = \tfrac12\left(1 + \sqrt {1+4n}\right) = \Theta(\sqrt{n})$$

Suppose we replace the $\sqrt$ operator with the following function:

$$f(n) = \sqrt{n \ln{n}}$$

What is an asymptotic bound on:

$$ f{(n+f{(n+f{(n+f{(n+\cdots)))}}}} $$ ?

1

There are 1 best solutions below

3
On BEST ANSWER

Let $L$ be the limit, then

$L=f(n+L)=\sqrt{(n+L)\ln (n+L)}$

$L^{2}=(n+L)\ln(n+L)$

By $GM \leq AM$,

$L<\frac{n+L+\ln(n+L)}{2} \implies L<n+\ln(n+L)$

It seems that $L=o(n)$.

Trying to expand the RHS asymptotically, by Mathematica or else:

$L^{2} = n\ln n+L(1+\ln n)+O \left( \frac{L^{2}}{n} \right)$

By quadratic formula,

$L \sim \frac{(1+\ln n)+\sqrt{(1+\ln n)^{2}+4n\ln n}}{2}$

$L= \sqrt{n\ln n}+\frac{\ln n+1}{2}+ O\left( \ln n \, \sqrt{\frac{\ln n}{n}} \right)$.