0
$\begingroup$

I'm trying to figure out how to prove the following but to no avail.

Given the following functions :

$f(n) = n^3 -4n$

$g(n) = 5n^2 + 3n$

I have to show that $g(n) = o(f(n))$ by definition, that is not using limits or O definitions.

Notice that we say that $f(n)$ is $o(g(n))$ if for any real constant $\epsilon > 0$, there exists an integer constant $n_0 >= 1$ such that $f(n) < \epsilon g(n)$ for every integer $n>=n_0$.

I was trying to use some calculus techniques to solve it.

Here is what I have so far:

I'm looking for $n_0 >= 1$ such that $\epsilon_0 >= (5n^2+3n)/(n^3-4n)$ for every $n>= n_0$

Can someone explain me how can I continue from here? If I solve this inequality I believe It will give me the required $n_0$ for the $\epsilon$.

2 Answers 2

2

For every $\varepsilon\gt0$, choose $n_\varepsilon\geqslant4$ such that $n_\varepsilon\geqslant8/\varepsilon$. Then, for every $n\geqslant n_\varepsilon$, $$ g(n)=5n^2+3n\leqslant8(n^2-4)=8f(n)/n\leqslant(8/n_\varepsilon)f(n)\leqslant\varepsilon f(n). $$ The only nontrivial step is the assertion that $5n^2+3n\leqslant8(n^2-4)$, but this is equivalent to the inequality $3n(n-1)\geqslant32$, which indeed holds for every $n\geqslant4$.

  • 0
    Can you please explain me how did you get to the nontrivial step. the assertion g(n) <= 8(n^2-4) and 8/n_epsilon2012-11-04
  • 1
    If $n\geqslant4$, then $3n(n-1)\geqslant3\cdot4\cdot3=36\geqslant32$ hence $3n^2\geqslant3n+32$ hence $8n^2-32\geqslant5n^2+3n$, QED.2012-11-04
  • 0
    Okay I'll think about this but just how did you get from 8(fn)/n to (8/n_epsilon)*f(n) ? the last part2012-11-04
  • 0
    Oh I understand. You assumed epsilon is bigger than 8/n_epsilon, right?2012-11-04
  • 0
    Yep, because one assumed at the onset that $n_\varepsilon\geqslant8/\varepsilon$. Crafty, eh... :-)2012-11-04
  • 0
    hehe , Thank you @did, helped me alot!2012-11-04
  • 0
    Did I'm not sure if it reasonable to ask this but How did you think of the first inequality? I understand anything you wrote here but I want to know if there is a technique leads you to this answer or only experience.2012-11-04
  • 0
    see my response above.2012-11-04
  • 1
    The answer is easy: I started from $g(n)\leqslant\varepsilon f(n)$ and tried to massage this inequality until it was somehow related to $n\geqslant$some function of $\varepsilon$. Naturally, a second phase was then necessary, which was to check that the path could be reverted, that is, that $n\geqslant$something **implied** $g(n)\leqslant\varepsilon f(n)$ (since this is the implication one is interested in).2012-11-04
0

Hint as $n$ tends to infinity

$$ \frac{5n^2+3n}{n^3-4n} \sim\frac{5n^2}{n^3}=\frac{5}{n} $$

  • 0
    Just to make sure I understand. This limitation caluclation allows me to detemine that my n_0 is bigger than 5/n ?2012-11-04
  • 1
    @Guy: Limits never yield values of $n_0$. This is because one can modify as many terms of a sequence as one wants (but a finite number) without changing the limit. Hence, if you think some $n_0$ works, change the $100n_0$ first terms and your $n_0$ does not work anymore. :-) To get some $n_0$, one needs *quantitative* methods (and fortunately, these exist).2012-11-04
  • 0
    Yes that's why I was so confused. Thank you for the clarfication.2012-11-04