Take the 2-minute tour ×
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.

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|improve this question
    
I don't think it's true either. What is "it?" –  daniel Feb 22 '13 at 23:29
1  
Or maybe you mean $\left(1-\frac{1}{n\log n}\right)^n$? –  mjqxxxx Feb 22 '13 at 23:37
1  
@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
1  
I may be confusing something... –  Guillermo Feb 22 '13 at 23:47
2  
With the new version, note that Robert Israel's answer is still suited to handle it. –  Jonas Meyer Feb 22 '13 at 23:53
show 2 more comments

5 Answers 5

up vote 13 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|improve this answer
add comment

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

share|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
1  
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
add comment

$$\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|improve this answer
add comment

$(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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.