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

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?

-
I don't think it's true either. What is "it?" – daniel Feb 22 '13 at 23:29
Or maybe you mean $\left(1-\frac{1}{n\log n}\right)^n$? – mjqxxxx Feb 22 '13 at 23:37
@Ryuichi: That still converges to $1$, hence is not $O(g(n))$ for any $g(n)$ converging to $0$. – Jonas Meyer Feb 22 '13 at 23:44
I may be confusing something... – Guillermo Feb 22 '13 at 23:47
With the new version, note that Robert Israel's answer is still suited to handle it. – Jonas Meyer Feb 22 '13 at 23:53

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)$$

-

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

-
how fantastic!! – Guillermo Feb 23 '13 at 0:21
I've been using Bernoulli's Inequality to good effect recently. Too bad you got to this first >8( – robjohn Feb 23 '13 at 1:01
It's a good one to have hanging on your tool belt. – Byron Schmuland Feb 23 '13 at 1:14
Well, I'm disproving the conjecture that the error is $O\left({1\over n}\right)$ and a lower bound does the trick. – Byron Schmuland Feb 23 '13 at 2:50

$$\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$$

-

$(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)$

-
Thank you for clarifying. I have deleted my obsolete comments. – Jonas Meyer Feb 22 '13 at 23:52
much clearer and elagant this last version. – Halil Duru Feb 22 '13 at 23:55

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)$.

-