1

This link is my previous attempt to prove this.

Question: if $\displaystyle\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=0$, then $f(n)$ is $o(g(n))$.

My proof:

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

$\Rightarrow$ $\displaystyle{0}\le{\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}}\lt{c}$ , $\forall{c}\gt{0}$

$\Rightarrow$ ${0}\le{\frac{\displaystyle\lim_{n\rightarrow\infty}f(n)}{\displaystyle\lim_{n\rightarrow\infty}g(n)}}\lt{c}$ , $\forall{c}\gt{0}$, $f$ and $g$ is real-valued function

$\Rightarrow$ $\displaystyle{0}\le{\lim_{n\rightarrow\infty}{f(n)}}\lt{c\lim_{n\rightarrow\infty}g(n)}$ , $\forall{c}\gt{0}$, $f$ and $g$ is real-valued function

$\Rightarrow$ $\displaystyle{0}\le{f(n)}\lt{{c}\cdot{g(n)}}$ , $\forall{c}\gt{0}$, $f$ and $g$ is real-valued function , $\forall{n}\ge{N}$, where N is big enough.

$\Rightarrow$ $\displaystyle{0}\le{f(n)}\lt{{c}\cdot{g(n)}}$ , $\forall{c}\gt{0}$, $\forall{n}\ge{N}$, $\exists{N\gt0}$

$\Rightarrow$ $f(n)\in{o(g(n))}$ $(\because o(g(n))\equiv\{f(x):\forall c>0, \exists n_0>0$ s.t. $0\le f(n)\lt cg(n), \forall n\ge n_0\})$

$\Rightarrow$ $f(n)=o(g(n))$

$\therefore$ if $\displaystyle\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=0$, then $f(n)$ is $o(g(n))$.

Is there any problem in my proof process?

I extremely want to prove this [rigorously and mathematically].

Thank you for reading.

Community
  • 1
Danny_Kim
  • 3,423

1 Answers1

0

The first error occurs when you assert that

$$ \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{\lim_{n \to \infty} f(n)}{\lim_{n \to \infty} g(n)}, $$

which is not true in general. Take, for example, $f(n) = n$ and $g(n) = n^2$.

The second error occurs when you try to multiply both sides of an inequality by $\lim_{n \to \infty} g(n)$, which may be $\infty$. This is not valid.

Third, the expression

$$ \lim_{n \to \infty} f(n) < c \lim_{n \to \infty} g(n) $$

can only be true if $\lim_{n \to \infty} f(n)$ is finite. This is not one of the usual assumptions on the theorem you are trying to prove, so writing an expression which depends on it is not valid.

Antonio Vargas
  • 24,993