1
$\begingroup$

There's lots of statements involving limits in basic real analysis that I don't know how to justify properly. For example: $$\lim_{x \rightarrow \infty} e^{-x} = 0, \qquad \lim_{x \rightarrow \infty} xe^{-x} = 0$$

$$\lim_{x \rightarrow \infty}\frac{x^3+3x-1}{2x^3-5x^2} = \lim_{x \rightarrow \infty}\frac{x^3}{2x^3}$$

I don't actually know why these kinds of statements are true, I just have a vague sense that some functions are more "powerful" than others.

Further to this, I get the feeling that big-O notation is relevant here but I've never managed to learn that properly. Also it seems to throw away too much information; if $O(x^3) = O(2x^3)$, then computing the above limit by a big-O argument seems to be impossible.

Question. How does one learn this stuff properly?

$\endgroup$
  • $\begingroup$ $e^x \ge 1+x \implies e^{-x}\le \frac1{1+x}$. And $xe^{-x}\le \frac{x}{1+x+x^2/2}$ for $x>0$. $\endgroup$ – Mark Viola May 11 '18 at 3:20
  • $\begingroup$ @MarkViola, that's a nice argument. But I really want a resource I can study from. $\endgroup$ – goblin May 11 '18 at 3:27
  • $\begingroup$ My understanding has always been that the Maclaurin series representations (in the case of $e^{-x}$, at least) allows for a rigorous evaluation of those limits. The third limit can be solved by factoring out $x^3$ in both the numerator and denominator and then making use of $\lim_{x \to \infty}{\frac{1}{x}}=0$. $\endgroup$ – Hayden May 11 '18 at 3:48
  • 3
    $\begingroup$ You seem mature enough mathematically to find a good book on elementary analysis. $\endgroup$ – Mark Viola May 11 '18 at 3:48
  • 3
    $\begingroup$ "But usually they're very theoretical" - that is a good thing when trying to learn something rigorously... $\endgroup$ – Math1000 May 11 '18 at 6:24
3
$\begingroup$

A readable introduction is given in section 3.7: The Order of Magnitude of Functions in R.Courants Classic Introduction to Calculus and Analysis, Vol. 1.

There he proves following

  • Theorem: If $a$ is an arbitrary number greater than one, then the qutient $\frac{a^x}{x}$ tends to infinity as $x$ increases.

He provides two different proofs explicitly indicating the importance of this theorem. From this theorem he derives the next two theorems:

  • The exponential function becomes infinite of a higher order of magnitude than any power of $x$.

  • The logarithm becomes infinite of a lower order of magnitude than any arbitrarily small positive power of $x$.

He continues:

On the basis of these results we can construct functions of an order of magnitude far higher than that of the exponention function and other functions of an order of magnitude far lower then that of the logarithm.

For example, the function $e^{\left(e^x\right)}$ is of a higher order than the exponential function, and the function $\log \log x$ is of a lower order than the logarithm; moreover we can iterate these processes as often as we like, piling up the symbols $e$ or $\log$ to any extent we please.

Together with the section 1.6 The Limit of a Sequence which covers some of your examples and the section 1.7 Further Discussion of the Concept of Limit you should have pretty much all the information you are looking for.

After reading this material the following statement in section 9.1. A Hierarchy from Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik might become more and more familiar:

We formalize this by saying that \begin{align*} f \prec g\quad\Longleftrightarrow \quad \lim_{n\to\infty}\frac{f(n)}{g(n)}=0 \end{align*} we have \begin{align*} 1\prec \log\log n\prec \log n\prec n^{\varepsilon}\prec n^c\prec n^{\log n}\prec c^n\prec n^n\prec c^{c^{n}} \end{align*} Here $\varepsilon$ and $c$ are arbitrary constants with $0<\varepsilon <1<c$.

$\endgroup$
1
$\begingroup$

How does one learn this stuff properly?

That is actually a fairly difficult and subjective question, because some learning methods work for some better than for others.

My personal opinion is not just reading a book about a certain topic, but doing the exercises, too. This may seem trivial to most readers, but I remember, as a beginner it's easy to think that "reading is enough". When you are able to prove most exercises in a book but a few, these may be worth looking up here on MSE, and asking them if no one else did.


Now, a part of me reads your above-cited question as

How does one learn this stuff rigorously?

Mizar is a proof assistant that can be used to let your proofs be verified by a computer, there you have to do it really rigorously and cannot mark something as "obvious", the checker would complain. You could learn Mizar and work with it to learn looking for the details, if that helps. The Mizar Mathematical Library already holds many theorems related to your topic where you could verify them in most detail, if wanted. The drawback is that it takes some time to learn Mizar and get used to it. The theory of Big Oh-Notation starts here. Results include $\mathcal O(\log_2 n)\subsetneq\mathcal O(\sqrt{n})$, $\mathcal O(n\log_2 n)\subsetneq \mathcal O(n^{1+\varepsilon})$, $\mathcal O(n^{\log_2 n})\subsetneq \mathcal O(n^\sqrt{n})$, $k\leq m \implies \mathcal O(n^k)\subsetneq\mathcal O(n^m)$, to name a few. My current research doesn't has so much to do with limits, so I'm afraid I can't provide a guide for the Mizar Mathematical Library in this regard (yet), but at least I could point you to where to start looking.


On a site note, regarding Big $\mathcal O$-Notation: it can be defined like this

$$g\in\mathcal O(f) :\iff \lim_{n\to\infty}\frac{f(n)}{g(n)}=c\in\mathbb R$$

So we get $g\prec f \iff g\in\mathcal O(f) \land f\notin\mathcal O(g)$, if you compare it the answer from Markus.

$\endgroup$
  • $\begingroup$ I don't know why this got a downvote, but I've annulled with my own countervote. Thanks for the answer. $\endgroup$ – goblin May 12 '18 at 0:28
  • $\begingroup$ @goblin I tend to ignore single downvotes on my answers without explanation. It's not worth worrying about. But thanks nevertheless :) $\endgroup$ – SK19 May 12 '18 at 5:06
  • $\begingroup$ :) $\;\;\!\!\;\!$ $\endgroup$ – goblin May 12 '18 at 5:15
  • $\begingroup$ +1 for the input on mizar. $\endgroup$ – Paramanand Singh May 12 '18 at 8:28

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.