$(1+\frac{1}{n\log n})^n-1=O(\frac{1}{n})$.

Question

When I solved a problem, I could solve it if I assumed that $(1+\frac{1}{n\log n})^n-1=O(\frac{1}{n})$

I tried to prove it, but I failed.

Actually, I don't convince if it is true.

Is it correct? If so, how to solve it?

Answer 1

It's not true. In fact $$\left(1 + \frac{1}{n \log n}\right)^n = \exp\left(\frac{1}{\log n}\right) + O\left(\frac{1}{n \log n}\right) = 1 + \frac{1}{\log n} + O\left(\frac{1}{\log(n)^2}\right)$$

Answer 2

$(1+1/(n \log(n))^n$ $\to 1 $ as $n\to\infty$.

So , $(1+1/(n \log(n))^n$ =$O(1)$$ $

Since the function doesn't converge to $0$ , we conclude that

$f(n)$$\neq O(1/n)$

Answer 3

$$\lim_n (1\pm \frac{1}{n\log n})^n=\lim_n [(1 \pm \frac{1}{n\log n})^{n\log(n)}]^\frac{1}{\log(n)}=(e^{\pm 1})^0=1 $$

Answer 4

Bernoulli's inequality gives $$\left(1+{1\over n\log(n)}\right)^n\geq 1+{1\over \log(n)}. $$

Answer 5

To show in an elementary way that your expression is actually of order $1/\log n$, I will use this "contra-Bernoulli" inequality:

If $n$ is a positive integer and $0 < x < 1/n$ then $(1+x)^n < 1/(1-nx)$.

This is readily proved by induction in the form $(1-nx)(1+x)^n< 1$.

Putting $x = 1/(n \log n)$, this becomes $(1+1/(n \log n))^n < 1/(1-n/(n \log n)) = 1/(1-1/\log n) = \log n/((\log n) - 1) $ so $(1+1/(n \log n))^n - 1 < \log n/((\log n) - 1)-1 = 1/((\log n) - 1) $.

Putting $a$ for $\log n$, this, combined with the regular Bernoulli's inequality, shows that, if $a > 1$ then $1/a < (1+1/(an))^n-1 < 1/(a-1)$.