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$.

  • 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
    Yes that's why I was so confused. Thank you for the clarfication.2012-11-04