1
$\begingroup$

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

Improve this question
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Augustin Sep 17 '15 at 14:33
  • $\begingroup$ @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$ $\endgroup$ – uniquesolution Sep 17 '15 at 14:35
  • $\begingroup$ 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? $\endgroup$ – ahorn Sep 17 '15 at 14:44
  • $\begingroup$ The solution is allready written out on the same line :D. $\endgroup$ – MrYouMath Sep 17 '15 at 14:58
  • $\begingroup$ @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. ;-)) $\endgroup$ – Mark Viola Sep 17 '15 at 15:17
1
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ Just curious .... how do "we know $\frac{\log y}{y}\to 0$" in the context of this question? $\endgroup$ – Mark Viola Sep 17 '15 at 15:12
  • $\begingroup$ That is a basic fact about logarithms, but I can show it if you're interested. $\endgroup$ – Bernard Sep 17 '15 at 15:16
  • $\begingroup$ Yes, I know various ways to show this. But, to improve your answer for the OP and other readers, it would be helpful to add one way. I do like your approach. ;-)) $\endgroup$ – Mark Viola Sep 17 '15 at 15:20
  • $\begingroup$ @Dr. MV: Added! $\endgroup$ – Bernard Sep 17 '15 at 15:34
  • $\begingroup$ Excellent. The approach aligns with the way forward that I posted. $\endgroup$ – Mark Viola Sep 17 '15 at 16:12
2
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ I think Augustin explains this better. $\endgroup$ – ahorn Sep 17 '15 at 14:54
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ What happens in the case $a>\delta$? I believe that we need the additional constraint $a<\delta$ here, do we not? $\endgroup$ – Mark Viola Sep 17 '15 at 15:08
  • $\begingroup$ Uh, I do not think so. :) $\endgroup$ – Megadeth Sep 17 '15 at 15:25
  • 1
    $\begingroup$ Well, first, how does $n^{a-\delta}<a\epsilon$ imply $n>(a\epsilon)^{a-\delta}$? And second, for $a>\delta$, $n^{a-\delta}\to \infty$. $\endgroup$ – Mark Viola Sep 17 '15 at 16:09
1
$\begingroup$

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!

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ Why does your numerator on the RHS have $x^\delta$ instead of $x^{-\delta}$? $\endgroup$ – ahorn Sep 18 '15 at 8:59
  • $\begingroup$ @ahorn Good catch on the typo. +1 for thw useful comment. I've edited $\endgroup$ – Mark Viola Sep 18 '15 at 13:53
  • $\begingroup$ My question was directed more at the inequality $\frac{\log n}{n^{\delta}}\leq 1$, and your response did not directly mention that inequality. $\endgroup$ – ahorn Sep 20 '15 at 14:41
  • $\begingroup$ @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. $\endgroup$ – Mark Viola Sep 20 '15 at 14:56

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.