How to show $3(\log_2 n)^5 < \sqrt{n}$

Question

I am teaching final year high school students and needed to persuade them of the following fact:

There exists an $n_0 > 0$ such that for all $n>n_0$,

$$3(\log_2 n)^5 < \sqrt{n}$$

Plotting the functions is no use and so I would love a mathematical argument they could follow.

---

Update

The students know how to differentiate but are not confident with L'Hôpital's rule. I thought about asking them to plug in values of $n$ but it seems you need $n \geq 8760381590675189248$ before the inequality is true!

Answer 1

From $$ \lim_{n\to\infty}\frac{\log_2 n}{n} = 0 $$ we get (for any numbers $a,b > 0$) $$ \lim_{n \to \infty}\frac{ab\log_2 n}{n} = 0 $$ which is to say $$ \lim_{n \to \infty}\frac{a\log_2 (n^b)}{n} = 0 $$ But write $m = n^b$ to get $$ \lim_{m \to \infty}\frac{a\log_2 m}{m^{1/b}} = 0 $$ now for any $c > 0$, $$ \lim_{m \to \infty}\frac{a^c(\log_2 m)^c}{m^{c/b}} = 0 $$ To do this problem, we want $a,b,c$ so that $c/b = 1/2$, $c=5$, $a^c = 3$. That is, $c=5, b=10, a=3^{1/5}$.

---

In general, any power of $\log n$, however big, is less than any positive power of $n$, however small.

$$ (\log n)^{1000000} < n^{0.0000001} $$ for large enough $n$.

Answer 2

I would first try to convince them that they are capable of thinking about the problem. Once you get past this hurdle, I think it will not be too bad.

To do so, start with a different example. Like:

Show that there exists an $n_0$ where for $n > n_0$,

$$\sqrt n > 100 + \log_7 n$$

My questions to the students would be:

• What kind of $n$ is easy to plug in to the left side? (Perfect squares)
• What kind of $n$ is easy to plug into the right side? (Powers of 7)
• Are there any perfect squares that are also powers of 7? (Yes, $7^2$, $7^4$, ...)

Try these. Try a bunch of them. The goal is to convince the students that they can play with the question.

Then build them up to $n = 7^{2k}$. When you plug this in, you are asking whether for large enough $k$,

$$7^k > 100 + 2k$$

This is easier to believe, it happens for, for example, $k \geq 3$.

---

For your example, $n = 2^{2k}$ should work, but for beginning students, the realization that they can plug in $n = 2^2$ and $n = 2^4$ and $n = 2^6$ to see what is happening before abstracting to $n = 2^{2k}$ would be my goal.

Answer 3

"Plotting the functions is no use"

It still might be worth it, after proving the cross-over by one of the several techniques suggested, to show the students a plot of the functions using software that permits arbitrary ranges. It helps the intuition to see the $\log$ function flatten while $\sqrt{n}$ steadily rises. Here I'm echoing @DavidButlerUofA.

---

^{Plotted in Mathematica.}

---

Answer 4

Since log base 2 appears, maybe look at the case $n=2^k$. Then $3(\log_2 2^k)^5$ simplifies to $3k^5$, which is a polynomial in $k$. For the other quantity, $\sqrt{n}$ simplifies to $2^{k/2}$, which is exponential in $k$. Since exponential growth eventually dominates polynomial growth, the inequality is plausible.

Answer 5

This may not be a satisfying answer, but you CAN do it graphically. If you draw $y= \frac{3(\log_2 x)^5}{\sqrt{x}}$ in Desmos, then you can zoom out far enough to see that it begins to decrease after about x=20 000. Then you can REALLY zoom the x-axis out and zoom the y-axis in until you can see that the value drops below 1 after $9 \times 10^{18}$. https://www.desmos.com/calculator/yb5ma3k7dj The slow reveal here might be rather compelling to high school students actually.

It might also be possible to convince them algebraically. Attempt to solve the inequality. $$ 3(\log_2(x))^5<\sqrt{x}\\ 9(\log_2(x))^{10}<x\\ 9^\frac{1}{10}\log_2(x)<x^\frac{1}{10}\\ $$ Let $u=x^\frac{1}{10}$ and then $$ 9^\frac{1}{10}\log_2(u^{10})<u\\ 9^\frac{1}{10}\cdot 10\log_2(u)<u\\ \frac{\log_2(u)}{u}<\frac{1}{10 \cdot9^\frac{1}{10}}\\ $$ Since $\log_2(u)$ grows much slower than $u$, that means $\frac{\log_2(u)}{u}$ gets smaller and smaller, so there will come a point where the left hand part is smaller than the right-hand part.

Answer 6

That $n$ will be big. To solve: $$\log_2(n)<\frac{n^\frac{1}{10}}{c}\quad\text{with $c=\sqrt[5]{3}$}.$$ As $n$ is argument of $\log$ and of a tenth root a well, an educated Ansatz for $n$ would be a number which covers both, that is, start with $$n=2^{10m}.$$ The inequality then becomes $$ 10m<\frac1c\cdot2^m.$$

As $c\approx1$ we are convinced -- and a trivial induction proves it -- that all $m\geq7$ will solve the inequality.
From here $n=2^{70}$.

NB: In case you want to show that any real $n>2^{70}$ will do, consider $f(x)=\frac{2^x}{c}-10x$. We know that $f(7)>0$. Now show that $f$ is strictly increasing for $$x>\frac{\ln\left(\frac{10}{\ln(2)}c\right)}{\ln(2)} \approx2.9.$$

Answer 7

1. I don't know of an algebraic way of proving this--think you need calculus.

2. Just trying some numbers is a way to see that the gap between the functions widens with n (and still exists even for very low n). Essentially the same point as just graphing the functions and/or their difference. But useful to divide the problem into less than and greater than 2 (where the log base 2 hits 1, and also below 1, where the log goes negative, but radical stays positive).

3. I question "why" to push this for pre-calculus kids (or at least pre-pre-calculus). This sort of topic belongs as a normal use of L'Hopital's equation. There is no major loss in not exposing kids to it earlier. If anything, maybe a gain in not confusing them. Not every hill needs to be taken in a given year of the war. Prioritize. (If the kids know calc, show them with L'Hopital, of course.)

4. If you really get a hair up, you could find the minimum difference, as a max/min problem. Take the derivative and set to zero. It gives you a hairy equation in n--I don't think soluble algebraically. But you can approximate it numerically.