5
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ Why the $3$ and the $5$? Shouldn't it work for all numbers, i.e. something along the lines of $\log_2 n < n^r$ after a certain point for every positive $r \in \mathbb{Q}$? Then you can add a number in front of the log later if needed. $\endgroup$ – Dirk Sep 9 '19 at 11:15
  • $\begingroup$ @RoryDaulton They can compute derivates but they don't know that the harmonic series is a good approximation for the natural logarithm/ $\endgroup$ – Anush Sep 9 '19 at 14:29
  • $\begingroup$ I'm not sure what you mean by "plotting the functions is no use". When I ask Desmos to plot them, I get this desmos.com/calculator/yohbt58kup and it seems that after n=2 you get that 3(log_2 n)^5 > sqrt(n). Am I missing something? $\endgroup$ – DavidButlerUofA Sep 9 '19 at 16:49
  • $\begingroup$ @DavidButlerUofA Right. But the point is that there exists an $n_0$ such that for all $n> n_0$, $3(\log_2 n)^5 < \sqrt{n}$. This is the opposite of the impression you get from plotting! $\endgroup$ – Anush Sep 9 '19 at 17:15
  • 4
    $\begingroup$ But why do you need to persuade them of this? Understanding your purpose might help us help you achieve it. $\endgroup$ – Sue VanHattum Sep 11 '19 at 2:59
6
$\begingroup$

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

| improve this answer | |
$\endgroup$
8
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ This makes sense but the problem is that when they plug in guesses they get that the right hand side is smaller than the left hand side. $\endgroup$ – Anush Sep 9 '19 at 14:24
  • $\begingroup$ Sure -- but if they plug in $7^2$, then $7^4$, then $7^6$, etc, then you (the instructor) may be able to convince them to try the general case: $7^{2k}$. At this point, the problem becomes more accessible. $\endgroup$ – Chris Cunningham Sep 9 '19 at 16:21
  • 2
    $\begingroup$ You mean that if they try $n = 2^{2k}$ in OPs example, they compare $96k^5$ to $2^k$. We've definitely improved the problem (the cutoff is something like k = 32 now) but I will admit that my step doesn't completely solve the problem unless the instructor allows the argument "exponentials beat polynomials." I look forward to other answers. $\endgroup$ – Chris Cunningham Sep 9 '19 at 22:00
  • 3
    $\begingroup$ I still think this is the right direction to go on matheducators.stackexchange.com though; a lot of the other answers are attempting to find a mathematically convincing argument, but missing out on the education part. $\endgroup$ – Chris Cunningham Sep 10 '19 at 14:14
  • 2
    $\begingroup$ I think this is a really good answer: getting to grips with a problem on a simpler case is often very helpful, and we should teach our students to do this (devise simpler similar question that are easier to answer to get a better idea). Here, maybe one can even start with a simpler question (e.g. when do we have $\sqrt{n} > \log_2(n)$), and progressively increase difficulty so that one sees the simpler question illuminates the last one; kind of a continuity method in education. $\endgroup$ – Benoît Kloeckner Sep 28 '19 at 8:31
6
$\begingroup$

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


LogSqrt
Plotted in Mathematica.


| improve this answer | |
$\endgroup$
  • $\begingroup$ I really should have committed to the the original graph showing both, shouldn’t I? $\endgroup$ – DavidButlerUofA Sep 10 '19 at 19:58
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
2
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ Welcome! The poster of the question indicated they are teaching high school students. Do you have any tips about how to get high school students through the kind of reasoning you have given? $\endgroup$ – Chris Cunningham Sep 26 '19 at 16:28
  • $\begingroup$ Of course, see my edit. $\endgroup$ – Michael Hoppe Sep 26 '19 at 16:35
  • $\begingroup$ and a trivial induction proves it --- This only shows the inequality is true for integers greater than or equal to $7.$ $\endgroup$ – Dave L Renfro Sep 27 '19 at 8:20
  • $\begingroup$ @DaveLRenfro As the OP talked about some $n_0$ I presumed that he was looking for a natural number. And the induction shows that one may choose $n_0=2^{70}$. $\endgroup$ – Michael Hoppe Sep 27 '19 at 8:31
  • $\begingroup$ OK. In looking back over the question itself (not comments, not other answers), I tend to agree. Indeed, for all we know, this could have been a problem when covering mathematical induction. I guess this is something else to add to the list of ambiguous aspects of the question, such as how rigorous persuade them is supposed to be. $\endgroup$ – Dave L Renfro Sep 27 '19 at 10:18
0
$\begingroup$
  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.

| improve this answer | |
$\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.