1

I am trying to understand this trick:

textbook photo

(You can ignore my handwriting)

WolframAlpha gives that $\displaystyle\lim_{n \to \infty} \frac {\log n}{n^\delta}=0$. If that is true, can you show me why? If this is the reasoning behind the inequality above, $1$ was probably chosen because the expression is less than $1$ for sufficiently large $n$.

On the other hand, Dahn Jahn has mentioned the inequality $$\log n < n^\delta$$ elsewhere on this site. But I do not know how to prove this. (WolframAlpha doesn't give a clear answer.)

EDIT: I do not need any answers explaining why $\frac{\log n}{n^{\delta}} \to 0$ because Augustin showed me that in the first comment, and I immediately understood. My question is why $1$ was chosen on the RHS of $\frac{\log n}{n^{\delta}}\leq 1$.

Community
  • 1
ahorn
  • 2,236
  • Hint: $\frac{\log n}{n^{\delta}}=\frac{1}{\delta}\frac{\log n^{\delta}}{n^{\delta}}$ and $\frac{\log N}{N}$ goes to $0$ as $N$ goes to $\infty$. – Augustin Sep 17 '15 at 14:33
  • @Augustin - The question included the case $\delta=1$. I guess the OP needs a formal proof that ${\log N\over N}\to 0$ as $N\to\infty$ – uniquesolution Sep 17 '15 at 14:35
  • No, thank you, I understand that $\displaystyle \lim_{N \to \infty}{\log N\over N}=0$ using l'Hospital's Rule. Is the choice of "$1$" arbitrary? – ahorn Sep 17 '15 at 14:44
  • The solution is allready written out on the same line :D. – MrYouMath Sep 17 '15 at 14:58
  • @ahorn If you understand that $\frac{\log x}{x}\to 0$ from L'Hospital's Rule, then why not use the same approach for $\frac{\log x}{n^{\delta}}$, $\delta>0$? It is in fact developed in the picture of the posted question. Alternatively, we can use the integral definition of the log function as in my answer. ;-)) – Mark Viola Sep 17 '15 at 15:17
  • @Dr.MV Augustin helped me to see that $\frac{\log n}{n^{\delta}} \to 0$. What I then wanted to know is why 1 was chosen on the RHS of the inequality. Is it an arbitrary choice? – ahorn Sep 18 '15 at 06:54

4 Answers4

2

Applying l'Hopital, we can easily check that for any $\delta>0$, we have $$\lim_{x\to\infty}\frac{\log x}{x^\delta}\ \overset{l'H}{=}\ \lim_{x\to\infty}\frac{1}{\delta}\cdot\frac{1}{x^\delta}=0.$$ Since this is true for $x\to\infty$, it must be true for $n\to\infty$. In fact, this argument will show any power of the logarithm over any positive power of $x$ will go to $0$.

Clayton
  • 24,751
1

It suffices to prove that for every $\delta > 0$ we have $\log(n)/n^{\delta} \to 0$. Let $a > 0$. If $n > 1$, then $$ 0 < \log n = \int_{t=1}^{n}\frac{1}{t} < \int_{t=1}^{n} t^{a-1} < \frac{n^{a}}{a}, $$ so $$ 0 < \frac{\log n}{n^{\delta}} < \frac{n^{a-\delta}}{a}. $$ Taking any $\varepsilon > 0$, we have $n^{a-\delta}/a < \varepsilon$ if $n > (a\varepsilon)^{a-\delta}$, so taking $N:= \lceil (a\varepsilon)^{a-\delta} \rceil$ suffices to ensure the convergence.

Yes
  • 20,719
1

Without L'Hospital: it is enough to show $\;\log\log n-\delta\log n\to-\infty$ in order to prove $\log n < n^\delta$. Now $$\log\log n-\delta\log n=\log n\Bigl(\frac{\log\log n}{\log n}-\delta\Bigr)$$ Setting $y=\log n$, we know $\dfrac{\log y}y\xrightarrow[y\to\infty]{} 0$, hence the second factor tends to $-\delta$ as $n$ tends to $\infty$, and the product tends to $-\infty$ as asserted.

Added: Why $\displaystyle\lim_{y\to\infty} \dfrac{\ln y}y=0$

We suppose $y>0$. Start from $\;\dfrac1t<\dfrac1{\sqrt t}$ if $\;t>1$. By the mean value inequality we have $$ \int_1^y \frac{\mathrm d\mkern1mu t}t=\ln y\le \int_1^y\frac{\mathrm d\mkern1mu t}{\sqrt t}=2\sqrt y-2<2\sqrt y$$ We deduce: $$0<\frac{\ln y}y<\frac2{\sqrt y}\xrightarrow[y\to\infty]{} 0$$

ahorn
  • 2,236
Bernard
  • 175,478
1

One approach is to define the logarithm function as

$$\log x=\int_1^x\frac{1}{t}\,dt \tag 1$$

for $x>0$. Then, we note that for any $\alpha<1$ and $x\ge1$, we have from $(1)$

$$\begin{align} \log x&\le\int_1^x\frac{1}{t^{\alpha}}\,dt\\\\ &=\frac{x^{1-\alpha}-1}{1-\alpha}\tag 2 \end{align}$$

For any $\delta>1-\alpha$ we have from $(2)$

$$\frac{\log x}{x^{\delta}}\le \frac{x^{1-\alpha-\delta}-x^{-\delta}}{1-\alpha}\to 0 \,\,\text{as}\,\,x\to \infty$$

Therefore, for any $\epsilon>$, there is a number $N$ such that whenever $n>N$,

$$\frac{\log n}{n^{\delta}}<\epsilon$$

Taking $\epsilon =1$, then $\frac{\log n}{n^{\delta}}<1$ whenever $n>N$. And we are done!

Mark Viola
  • 179,405
  • 1
    Why does your numerator on the RHS have $x^\delta$ instead of $x^{-\delta}$? – ahorn Sep 18 '15 at 08:59
  • @ahorn Good catch on the typo. +1 for thw useful comment. I've edited – Mark Viola Sep 18 '15 at 13:53
  • My question was directed more at the inequality $\frac{\log n}{n^{\delta}}\leq 1$, and your response did not directly mention that inequality. – ahorn Sep 20 '15 at 14:41
  • @ahorn We only need to set $x=n$ and we have it. This is because we have for any $\epsilon>$, there is an $N$ such that whenever $n>N$ we have $$\frac{\log n}{n^{\delta}}<\epsilon$$Now take $\epsilon =1$. I edited the answer to accommodate your request. – Mark Viola Sep 20 '15 at 14:56