1

I am trying to prove the following statement.

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

My solution

$o\left(g(n)\right)=\{f(n):\forall c>0, \exists n_0, \forall n>n_0, 0 \le f(n) \lt cg(n)\}$

$0 \le f(n) \lt cg(n)$ $\Leftrightarrow$ $0 \le \displaystyle\frac{f(n)}{g(n)} \lt c$ $\Leftrightarrow$ $\displaystyle \lim_{n\rightarrow\infty}0 \le \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)} \le \lim_{n\rightarrow\infty}c$

$\displaystyle\Leftrightarrow$ $0 \le \displaystyle\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)} \le c$

$\displaystyle\Leftrightarrow$ $0 \le \displaystyle\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)} \le 0$ ($\because$ c is any positive constant number)

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

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

Is my solution right mathematically?

I was wondering if there exists any holes in my process.

(e.g. omitting any conditions)

Thank you for reading my question.

Danny_Kim
  • 3,423
  • Not all equivalences are clear. For example, why $0\le \lim f/g\le c$ $\Rightarrow$ $0\le f/g<c$? Note that you need only to prove the implication. Better to do it by definition of $\lim$. – A.Γ. Sep 25 '15 at 14:13
  • @A.G. Thanks for your comment. You mean I proved only one way, right? So, do I have to show other way as well? – Danny_Kim Sep 25 '15 at 14:16
  • One way is not very clear either. When you say $0\le f/g<c$ $\Rightarrow$ $0\le\lim f/g\le c$ you need to justify first that the limit exists. The condition $\forall c>0$ is vital here for existence. Better way: start with the limit and write down carefully the definition of limit is zero in terms of $\forall\epsilon>0$ etc – A.Γ. Sep 25 '15 at 14:32
  • @A.G. I think I have to read limit first in wikipedia. Thank you :) – Danny_Kim Sep 25 '15 at 14:37
  • I posted again with new proof. link – Danny_Kim Sep 25 '15 at 17:02

1 Answers1

3

By definition $\lim_{n\to+\infty}a_n=A$ means that $$ \forall\epsilon>0\ \exists n_0\in\mathbb{N}\ \forall n\ge n_0\colon |a_n-A|\le\epsilon. $$

Apply it to $\lim_{n\to+\infty}\frac{f(n)}{g(n)}=0$ $$ \forall\epsilon>0\ \exists n_0\in\mathbb{N}\ \forall n\ge n_0\colon \underbrace{\left|\frac{f(n)}{g(n)}\right|\le\epsilon}_{\Leftrightarrow\ |f(n)|\le\epsilon|g(n)|} $$ and compare what you've got with the definition of the Little-O notation to conclude that $$ f(n)=o(g(n)), \ n\to+\infty. $$

A.Γ.
  • 29,518