7
$\begingroup$

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?

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

5 Answers 5

14
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

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

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you for clarifying. I have deleted my obsolete comments. $\endgroup$ Feb 22, 2013 at 23:52
  • $\begingroup$ much clearer and elagant this last version. $\endgroup$
    – Halil Duru
    Feb 22, 2013 at 23:55
3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .