2
$\begingroup$

This would be equal to:
$\forall c>0: \exists n_0 \in \mathbb{N}: \forall n>n_0: c\log(n) ≤ \frac{n}{\log(n)}$

For $c=1$ this is obvious, because
$\log(n) ≤ \sqrt{n} = \frac{n}{\sqrt{n}} ≤ \frac{n}{\log(n)}$

This estimation doesn't seem to work for $c>1$ though.
Any ideas on how I could prove it for $c>1$ ?

$\endgroup$
  • $\begingroup$ You just have to wait longer (choose $n_0$ larger). $\endgroup$ – Thomas Apr 27 '14 at 12:47
3
$\begingroup$

Using limits:

$$\lim_{n\to\infty}\frac{\log n}{n/\log n}=\lim_{n\to\infty}\frac{\log^2n}n=0 $$

because, for example, looking at the real functions $\;\log^2x\;,\;\;x\;$ , we have by l'Hospital:

$$\lim_{x\to\infty}\frac{\log^2x}x\stackrel{\text{l'H}}=\lim_{x\to\infty}\frac{2\log x}x\stackrel{\text{l'H}}=\lim_{x\to\infty}\frac2x=0\;\;\ldots$$

$\endgroup$
2
$\begingroup$

Note that $$\lim_{x\to+\infty}\frac{\ln x}x=0$$ Therefore also $$\lim_{x\to+\infty}\frac{(\ln x)^2}{x}=4\lim_{x\to+\infty}\frac{(\ln\sqrt x)^2}{x} =4\left(\lim_{x\to\infty}\frac{\ln\sqrt x}{\sqrt x}\right)^2=0.$$ Especially, for any $c>0$ we have $\frac{(\ln n)^2}{n}<\frac1c$ for almost all $n$, i.e. $c\ln n<\frac{n}{\ln n}$ for almost all $n$.

$\endgroup$
1
$\begingroup$

For $n$ big enough: $$\log(n) \leq \sqrt[4]{n} \Rightarrow \log(n) \leq \frac{\sqrt{n}}{\log(n)} < \epsilon \frac{n}{\log(n)}$$

$\endgroup$
1
$\begingroup$

$$ \frac{\log n}{\frac{n}{\log n}} = \frac{(\log n)^2}{n} \xrightarrow[n\to\infty]{}0 $$ so for all $c>0$, there exists $N_c \geq 0$ such that $\forall n\geq N_c$ one has $c\log n \leq \frac{n}{\log n}$.

Incidentqlly, this is an alternate definition of $o(\cdot)$ at a point $a\in\mathbb{R}\cup\{\pm\infty\}$ (for functions $g$ which cancel at most a finite number of time in the neighborhood of the point $a$): $f=o(g)$ if and only if $\frac{f}{g} \xrightarrow[a]{}0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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