Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
Can you please explain me how did you get to the nontrivial step. the assertion g(n) <= 8(n^2-4) and 8/n_epsilon –  SyndicatorBBB Nov 4 '12 at 14:20
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. –  Did Nov 4 '12 at 14:22
    
Okay I'll think about this but just how did you get from 8(fn)/n to (8/n_epsilon)*f(n) ? the last part –  SyndicatorBBB Nov 4 '12 at 14:24
    
Oh I understand. You assumed epsilon is bigger than 8/n_epsilon, right? –  SyndicatorBBB Nov 4 '12 at 14:26
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). –  Did Nov 4 '12 at 15:21

Hint as $n$ tends to infinity

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

share|improve this answer
    
Just to make sure I understand. This limitation caluclation allows me to detemine that my n_0 is bigger than 5/n ? –  SyndicatorBBB Nov 4 '12 at 12:30
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). –  Did Nov 4 '12 at 14:27
    
Yes that's why I was so confused. Thank you for the clarfication. –  SyndicatorBBB Nov 4 '12 at 14:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.