# Proving $\log n \leq n^\delta$ for $\delta > 0$, $n$ big

I am trying to understand this trick:

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

• 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

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

• Just curious .... how do "we know $\frac{\log y}{y}\to 0$" in the context of this question? – Mark Viola Sep 17 '15 at 15:12
• That is a basic fact about logarithms, but I can show it if you're interested. – Bernard Sep 17 '15 at 15:16
• 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. ;-)) – Mark Viola Sep 17 '15 at 15:20
• @Dr. MV: Added! – Bernard Sep 17 '15 at 15:34
• Excellent. The approach aligns with the way forward that I posted. – Mark Viola Sep 17 '15 at 16:12

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

• I think Augustin explains this better. – ahorn Sep 17 '15 at 14:54

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.

• What happens in the case $a>\delta$? I believe that we need the additional constraint $a<\delta$ here, do we not? – Mark Viola Sep 17 '15 at 15:08
• Uh, I do not think so. :) – Megadeth Sep 17 '15 at 15:25
• 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$. – Mark Viola Sep 17 '15 at 16:09

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!

• Why does your numerator on the RHS have $x^\delta$ instead of $x^{-\delta}$? – ahorn Sep 18 '15 at 8: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