$\frac{1}{n}$是$O(\frac{1}{\ln n})$还是$o(\frac{1}{\ln n})$？如何证明相关极限？

Hey there! Let's work through this problem step by step to get a clear answer. First, let's recap the definition of little-o notation: a function $f(n)$ belongs to $o(g(n))$ as $n \to \infty$ if and only if:
$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$$

In your case, $f(n) = \frac{1}{n}$ and $g(n) = \frac{1}{\ln n}$. Let's compute the ratio we need to evaluate:
$$\frac{f(n)}{g(n)} = \frac{\frac{1}{n}}{\frac{1}{\ln n}} = \frac{\ln n}{n}$$

So the core question reduces to proving that $\lim_{n \to \infty} \frac{\ln n}{n} = 0$. Here are two straightforward, rigorous ways to do this:

Method 1: L'Hôpital's Rule #

As $n$ approaches infinity, both $\ln n$ and $n$ tend to infinity—this gives us an $\frac{\infty}{\infty}$ indeterminate form, which fits the conditions for L'Hôpital's Rule. We take the derivative of the numerator and denominator separately:

• The derivative of $\ln n$ with respect to $n$ is $\frac{1}{n}$
• The derivative of $n$ with respect to $n$ is $1$

Applying the rule, our limit simplifies to:
$$\lim_{n \to \infty} \frac{\frac{1}{n}}{1} = \lim_{n \to \infty} \frac{1}{n} = 0$$

Method 2: Substitution & Growth Rate Argument #

Let's substitute $t = \ln n$, which means $n = e^t$. As $n \to \infty$, $t$ also approaches infinity. Rewriting the limit in terms of $t$ gives us:
$$\lim_{t \to \infty} \frac{t}{e^t}$$

Exponential functions like $e^t$ grow far faster than linear functions like $t$. To make this rigorous, use the Taylor series expansion of $e^t$:
$$e^t = 1 + t + \frac{t^2}{2!} + \frac{t^3}{3!} + \dots$$
For $t > 0$, $e^t > \frac{t^2}{2}$, so $\frac{t}{e^t} < \frac{2}{t}$. Since $\lim_{t \to \infty} \frac{2}{t} = 0$, the original limit must also be 0.

Final Conclusion #

Since $\lim_{n \to \infty} \frac{\ln n}{n} = 0$, by the definition of little-o notation, we can definitively say that $\frac{1}{n} = o\left(\frac{1}{\ln n}\right)$.

内容的提问来源于stack exchange，提问作者user425181