How to prove $\frac15 n^2-42n-8\in Ω(n^2)$?

Question

Here is my procedure:

So we want to prove $\exists c\in\Bbb{R^+}:\ [\exists B\in\Bbb{N}:[\ \forall n\in\Bbb{N}:\ n\ge B\rightarrow \frac15 n^2-42n-8\ge cn^2]]$

Taking $B=1$. We have $\frac15 n^2-42n-8\ge \frac15 n^2-42n^2-8n^2=\frac{-249}{5}n^2$. But here $c\notin \Bbb{R^+}$. How should we prove it?

Answer 1

Look at your statement carefully: We need a $c$ first, then we need a $B$. So let's first pick our $c$.

Take $c=\frac{1}{6}$, then solve the equation $\frac{1}{5}n^2-42n-8 \geq \frac{1}{6}n^2$, namely find the roots of the resulting quadratic equation $\frac{1}{30}n^2-42n-8$, which are $1260.19$ and $-0.19$ respectively. Hence,for $n \geq B=1261$, we get that $\frac{1}{5}n^2-42n-8 \geq \frac{1}{6}n^2$, because the function $\frac{1}{30}n^2-42n-8$ is increasing after the point $n=1261$, and so the inequality will remain.

By the way, there is nothing special about $\frac{1}{6}$. You can put what you like in there, as long as it's less than $\frac{1}{5}$! As an exercise, try out the fraction $\frac{1}{7}$ and see the $n$ you get.

Your mistake was to fix the $B$ first. Next time, look at the statement more carefully before making a call on your existential variables.

Answer 2

$1/5n^2−42n−8≥cn^2$, $n \geq B$ for some $B$ so $(1/5 -c)n^2 \geq 42n + 8$, if c is very small and closed to 0, then $n \geq 211$ satisfies the equation. Set this as base case.

Induction hypothesis: for $k \geq 211$, the proposition holds.

Induction step: then consider $k+1$, we have $1/5(k+1)^2 - 42(k+1) - 8 = (1/5k^2-42k-8) + (1/5 + 2/5k -8)$ if c is very small and closed to 0, $(1/5 + 2/5k -8) > 2ck + c$.

Hence, $(1/5k^2-42k-8) + (1/5 + 2/5k -8) \geq ck^2 + 2ck + c = c(k+1)^2$