0
$\begingroup$

I need to prove by definition (show that for every $C$ there exists a $n_0$) that: $$5n^2+3n= o(n^3-4n)$$

By trying to simplify the expression I get to the point where I should prove that: $$ \frac{5n^2+3n}{n^3-4n} < C$$.

Now, showing that $\lim\limits_{x\to\infty} \frac{5n^2+3n}{n^3-4n} = 0$ isn't a tough mission, but how do I prove it by definition? How do I point out specific $n_0$ for every $C$ that comes up? I'm asked to provide a tight answer and not let $n_0 = C^C$ so that the $n_0$ for sure will be large enough but to point out $n_0$ that is reasonably small.

$\endgroup$
4
$\begingroup$

Either you do what David suggested, or you do something like this:

Let $c > 0$. Then

\begin{align} 5n^2 +3n &\le c(n^3-4n) &\iff \\ 5n+3 &\le cn^2-4c &\iff \\ 0 &\le cn^2-5n-(3+4c) \end{align}

Now solve for $n$ and let $n_0$ be the bigger root of that term.

$\endgroup$
  • $\begingroup$ After finding the root, what is the method of proving that that root actually works for every $n$ that is bigger or equals to that root? $\endgroup$ – Eran Oct 28 '13 at 15:52
  • $\begingroup$ @Quaker: monotonicity. $\endgroup$ – G. Bach Oct 28 '13 at 16:06
  • $\begingroup$ Could you please explain a little deeper? The square root of the following function is $\frac{5+\sqrt{16c^2+12c+25}}{2c}$, how can I substitute $n$ with this expression? $\endgroup$ – Eran Oct 28 '13 at 16:16
  • 1
    $\begingroup$ @Quaker The function $f$ defined by the term $f(n) = cn^2 -5n -(3+4c)$ is monotonously increasing after its larger root for any $c>0$ as can for example be shown analytically by using the derivative (we don't have to worry about differentiability since we can just consider $f$ to be defined on $\mathbb{R}$, get the result there and then restrict its domain to $\mathbb{N}$). $\endgroup$ – G. Bach Oct 28 '13 at 16:21
  • 1
    $\begingroup$ @Quaker Yes, it will; if you'd like to picture it, the graph of that term is a parabola that opens up. $\endgroup$ – G. Bach Oct 28 '13 at 16:26
2
$\begingroup$

You don't have to prove every single step by definition. So, prove that the limit is zero and then use the definition of "the limit as $x$ goes to infinity is zero" to show that the definition of $o(-)$ is satisfied.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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