TAOCP 1.2.11.2 Exercise 11
Equation (18) states \sqrt[n]{n} = e^{\ln n/n} = 1 + \frac{\ln n}{n} + O\!
Section 1.2.11.2: Euler's Summation Formula
Exercise 11. [M11] Explain why Eq. (18) is true.
Verified: yes
Solve time: 44s
Solution
Equation (18) states
$$ \sqrt[n]{n} = e^{\ln n/n} = 1 + \frac{\ln n}{n} + O!\Big((\ln n/n)^2\Big). $$
We justify this by applying the Taylor series for the exponential function at zero. Let $x = \ln n / n$. Then $x \to 0$ as $n \to \infty$. By the standard expansion
$$ e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots, $$
we have
$$ e^x = 1 + x + O(x^2). $$
Substituting $x = \ln n / n$ yields
$$ e^{\ln n / n} = 1 + \frac{\ln n}{n} + O!\Big((\ln n / n)^2\Big), $$
which is exactly the claimed formula. The remainder term $O((\ln n/n)^2)$ accounts for all higher-order terms in the expansion, and it tends to zero faster than $\ln n / n$ because
$$ \lim_{n \to \infty} \frac{(\ln n / n)^2}{\ln n / n} = \lim_{n \to \infty} \frac{\ln n}{n} = 0. $$
This completes the proof.
∎