Disprove $n \in \Omega(n^2)$ I have a proof that I need to say what is wrong:
We will prove by induction on $n$, that there exists a constant $c > 0$ such that for every $n ≥ 4$ it holds that $n ≥ c · n^2$
Base case: for $n = 4$, for $c = \frac{1}{4}$ it holds.
Induction hypothesis: Assume that the claim is correct for $n−1$, meaning there exists $c_1 > 0$ such that $(n − 1) ≥ c_1(n − 1)^2$
Induction Step: We will show the proof is correct for $n$:
$n = n − 1 + 1 ≥ c_1(n − 1)^2 + 1 ≥ c_1 · (n^2 − 2n) ≥ c_1 · (n^2 − \frac{n^2}{2}) = \frac{c_1}{2}·n^2$
The last inequality is because for every $n ≥ 4$ it holds that $2n < \frac{n^2}{2}$. Hence, taking $c = \frac{c_1}{2}$ we have that $n ≥ c·n^2$.
I think that the worng thing here, is by taking $c=\frac{c_1}{2}$, but I'm not really sure about it.
Any help?
Thanks!
 A: Yes, taking $c=\frac c2$ is the problem here. To see that, we need to be more careful about what we do in the induction.
There are two statements you could prove:

*

*There is a $c>0$, so that for all $n\geq4$, $n\geq cn^2$.

*For all $n\geq4$, there is a $c>0$, so that $n\geq cn^2$.

The first is what you want, the second is what your induction proved.
Roughly speaking, you need to work your way from the outside in. So if you prove the first statement, first you need to pick some $c$ (say you pick $\frac14$). And then you need to show:

*

*Base case: For $n=4$, we have $n\geq \frac14n^2$. (Works.)

*Induction step (for $n\geq 4$): If $n\geq \frac14n^2$, then $n+1 \geq \frac14(n+1)^2$. (Does not work.)

So your induction gets stuck trying to prove this.
But if you try to prove the second statement, your induction looks a bit different. You need to show:

*

*Base case: For $n=4$, there exists a $c>0$ such that $n\geq cn^2$. (Works, namely $c=\frac14$.)

*Induction step (for $n\geq 4$): If there exists a $c>0$ such that $n \geq cn^2$, then there exists a $c>0$ such that $n+1 \geq c(n+1)^2$.

Now the induction step works because you don't need to stick to a fixed $c$. Instead, you can take the $c$ that exists by "there exists a $c>0$ such that $n \geq cn^2$" and construct from it a new $c$ for "there exists a $c>0$ such that $n+1 \geq c(n+1)^2$", namely $c_\mathit{new}:=\frac{c_\mathit{old}}2$ in your proof.
Rule of thumb: Anything that is quantified inside the "forall $n$" can be changed during induction. What is quantified outside cannot.
Exception: When we have an all-quantifier (e.g., "forall $c>0$, forall $n\geq 4$, something holds") you may often see that in proofs that the $c$ changes in the induction step (like you did in your proof)? Why is that allowed? Simple: if you do that, you are actually proving "forall $n\geq 4$, forall $c>0$, something holds" by my argument above. But that is equivalent to "forall $c>0$, forall $n\geq 4$, something holds" by the rules of all-quantifiers. So it's OK to prove one or the other. (But if you would be extremely formal, you would have to explicitly say that you prove "forall $c>0$, forall $n\geq 4$, something holds" and then add another proof step to go to "forall $c>0$, forall $n\geq 4$, something holds".)
A: The problem is that you are not picking the same constant $c_1$ for all values of $n$, which you should.
The definition is : $\exists c > 0 \, \forall n \, (n \geq c n^2)$
Your induction only proves that $\forall n \, \exists c > 0 \, (n \geq c n^2)$, which is much weaker.
In fact, here you can check that $\frac{n}{n^2} = \frac{1}{n} \rightarrow_{n \rightarrow \infty} 0$.
Then, you can reason as follows :
If $f(n) \geq c g(n) > 0$ for all (sufficiently large) $n$, and $f(n), g(n) > 0$, and $\frac{f(n)}{g(n)} \rightarrow 0$, then $\lim\limits_{n \rightarrow \infty} \frac{f(n)}{g(n)} \geq c$, i.e. $c \leq 0$.
