Proofs on growth rates of functions theorems using definition of a limit

[ATroelstein]

Hello, I am working through some proofs from the following document: Function Definitions

Under Calculation of Big - Oh, some theorems are provided that classify the growth rates of functions in relation to one depending on what the limit is as the input approaches infinity. One proof is provided when the limit is a constant using the definition of a limit, but I'm trying to also prove the others ones, such as when the limit is 0. I came up with the following proof, skipping restating some of the definition that has already been provided in the example proof.

$$
\frac{f(x)}{g(x)} - 0 < \epsilon
$$

$$
\epsilon = 1
$$

$$
\frac{f(x)}{g(x)} - 0 < 1
$$$$
\frac{f(x)}{g(x)} < 1
$$$$
f(x) < 1 * g(x)
$$

Which shows 1 is the constant and N0 is the N that I need to then prove this is correct using the definition of Big Oh. My question is, does my proof flow correctly? Also, are you technically able to pick any positive value for epsilon, or is there a technique involved with selecting this value. Lastly, what would the proof look like if the limit was infinity? I'm confused when I set up the initial part of that proof as the f(x)/g(x) would be minus infinity. Thanks in advance for any guidance.

 

[Evgeny.Makarov]

To start, why don't you state the claim that you are trying to prove?

 

[ATroelstein]

The claim I am trying to prove is that if:

$$
\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} = 0
$$

Then f(x) = O(g(x)) using the definition of a limit and then using the definition of Big Oh where the definition of Big Oh is:

f(x) = O(g(x)) if and only if there is a constant, c > 0, and an N >= 0, such that for all x > N, f(x) <= c*g(x)

 

[Evgeny.Makarov]

I am assuming we are considering nonnegative functions.

OK, you are right that you can choose c = 1. I did not understand this:

N0 is the N that I need to then prove this is correct using the definition of Big Oh.

I guess $N_0$ comes from the definition of the limit in the case of $\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} = 0$. Then I agree.

In general, unless you a computer, a proof should not be just a sequence of formulas. It should be a grammatically correct English text that includes phrases like "We must show that," "Suppose," "Therefore," "Set ε = 1," etc.

Also, are you technically able to pick any positive value for epsilon, or is there a technique involved with selecting this value.

Technically, yes, when you have an assumption or a proved claim that starts with "For every ε > 0," you can instantiate ε with any positive number. My calculus teacher used to say, "Let's pick an arbitrarily small ε, for example, ε = 100." Which ε can help move the proof forward depends entirely on the problem.

Lastly, what would the proof look like if the limit was infinity? I'm confused when I set up the initial part of that proof as the f(x)/g(x) would be minus infinity .

For example, if $\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} = \infty$, then $g(x)=O(f(x))$. Indeed, the assumption says that for every $M>0$ there exists an $N>0$ such that for all $x>N$ it is the case that $f(x)/g(x)>M$. Choose $M = 1$ and get the corresponding $N$; then $g(x)<f(x)/M=f(x)=1\cdot f(x)$ for all $x>N$.