Is $|g(n)| \le c \cdot |f(n)| \iff \lim_{n \to \infty} \frac {g(n)} {f(n)} = c $ true?

Question

I want to show that:

$|g(n)| \le c \cdot |f(n)| \iff \lim_{n \to \infty} \frac {g(n)} {f(n)} = c\mid c \in \mathbb R_0^+ \land n \in \mathbb N \land f,g: \mathbb N \to \mathbb R_0^+$

Due to the defined sets it's the same as:

$g(n) \le c \cdot f(n) \iff \lim_{n \to \infty} \frac{g(n)}{f(n)} = c$

Now I can make it look similar:

$g(n) \le c \cdot f(n) \iff \lim_{n \to \infty} g(n) = \lim_{n \to \infty} c \cdot f(n)$

But I'm not feeling confident enough about the rules of limits to determine the given term as true.

Answer 1

No, that is not correct. First, the left hand side has to hold only asymptotically, i.e., for all $n \geq n_0$.

Definition (Limit). We say that a real sequence $(x(n))_n$ converges to $c$ if for every $\epsilon>0$ there is a $n_0 = n_0(\epsilon)$ so that $|x(n) - c| < \epsilon$ for all $n\geq 0$. (Source: Wikipedia)

Then, from the definition of the limit, since $g(n)/f(n) \to c$, for every $\epsilon$ there is a $n_0$ so that for all $n\geq n_0$, $|g(n)/f(n) - c|<\epsilon$, which implies that $$ \begin{aligned} &\left|\frac{g(n)}{f(n)} - c\right|<\epsilon\\ \Rightarrow&\frac{g(n)}{f(n)} - c\leq \epsilon.\end{aligned} $$ And taking the infimum with respect to $\epsilon>0$ on both sides we have $$ \frac{g(n)}{f(n)} \leq c\tag{1}\label{1} $$ Now, for the converse, if you assume that \eqref{1} holds, you only have $$ \limsup_{n\to\infty}\frac{g(n)}{f(n)} \leq c\tag{2}\label{2}, $$ and if the limit exists, $\lim_{n\to\infty}{g(n)}/{f(n)} \leq c$

Answer 2

Example: $g(n)=n$ and $f(n)=3n$. Then $g(n) \le f(n)$ ($c=1$)

But $\frac{g(n)}{f(n)}= 1/3$

Answer 3

A major flaw in your assertion I feel have not been touched upon yet: the uniqueness of $c$

The first statement says that $|g(n)| \leq c |f(n)|$. Such $c$ is never unique, due to the following inequalities: $$|g(n)| \leq c|f(n)| \leq c|f(n)| + c'|f(n)| = (c+c')|f(n)|$$ where $c' \geq 0$. If the inequality holds for some $c$, it also holds for all $c' \in [c,+\infty)$.

Howver, the second statement is $$\lim_{n \to \infty} \frac{g(n)}{f(n)} = c.$$

But a limit, if it exists, is unique! It cannot be all values in the interval $[c,+\infty)$ at the same time!

Answer 4

(1).If $c>0$ then $|g(n)|\leq c|f(n)|$ does not imply that $\lim_{n\to \infty}|g(n)/f(n)|$ exists. E.g. $f(n)=2$ when $n$ is even, and $f(n)=1$ when $n$ is odd, with $g(n)=1$ for all $n,$ and $c=2.$

(2). If $c>0$ and $|g(n)|<c|f(n)|$ and if the limit $\lim_{n\to \infty}|g(n)/f(n)|$ does exist, the limit may be any $r\in[0,c].$ E.g. for $r\in (0,c]$ let $g(n)=rf(n)$ for all $n.$ And for $r=0$ let $g(n)=cf(n)/n$ for $n\in \mathbb N.$