Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 14 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer
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 $$

share|cite|improve this answer

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

share|cite|improve this answer
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)$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.