1. ## Help disproving this

I was able to complete the previous problems thanks to help from here. Here is the final problem set I'm stuck on:

To me it seems that there will always be a positive c so that cg(n) is greater or equal to f(n). No matter how large n is, since there's no limit to how large c can be (can even be a decimal), wouldn't that always be possible?

Thanks.

2. Originally Posted by Selena
I was able to complete the previous problems thanks to help from here. Here is the final problem set I'm stuck on:

To me it seems that there will always be a positive c so that cg(n) is greater or equal to f(n). No matter how large n is, since there's no limit to how large c can be (can even be a decimal), wouldn't that always be possible?

Thanks.
c is fixed.

3. Why is c fixed? Can't c be any positive real number?

4. Originally Posted by Selena
Why is c fixed? Can't c be any positive real number?
Any fixed positive real number, yes.

5. The issue is the order of quantifiers in the statement that has to be disproved. The statement says that there exist the same $c$ and $B$ that work for all $n\ge B$.

To me it seems that there will always be a positive c so that cg(n) is greater or equal to f(n). No matter how large n is, since there's no limit to how large c can be
Here you are saying that for all $n$ there exist its own $c$ that validates the statement. That would correspond to $\forall n\exists c\,f(n)\le cg(n)$. However, this is not what is claimed. Since $\exists c$ comes before $\forall n$, one has to choose $c$ first, and it has to work for all $n$.

6. Originally Posted by emakarov
The issue is the order of quantifiers in the statement that has to be disproved. The statement says that there exist the same $c$ and $B$ that work for all $n\ge B$.

Here you are saying that for all $n$ there exist its own $c$ that validates the statement. That would correspond to $\forall n\exists c\,f(n)\le cg(n)$. However, this is not what is claimed. Since $\exists c$ comes before $\forall n$, one has to choose $c$ first, and it has to work for all $n$.
Ooooh! That nailed it. Yeah I thought it meant any c would work, after you've chosen an n.
I guess it applies the same to this problem right?

(Oops ignore the "|" after the N)

This is what I have for it so far:

7. I think the solution to the second problem is correct: you choose c and B that work for all n.

8. Ah I'm kind of stuck on how to disprove the other one... =/
Any tips would be greatly appreciated.

9. It is convenient first to move negation inside the formula. For this, every quantifier has to be replaced by the opposite one, and the final implication $A\Rightarrow B$ has to be replaced by $A\land\neg B$. In this example, we get

$\forall c\in\mathbb{R}^+,\,\forall B\in\mathbb{N},\,
\exists n\in\mathbb{N},\,n\ge B\land f(n)>cg(n)$
.

So we have to produce a function that, given $c$ and $B$ will return the required $n$. Let's first leave out the condition $n\ge B$ and just find $n$ such that $f(n)>cg(n)$.

Given $c$ and $B$, let's find the points of intersection of $f(n)$ and $cg(n)$. By equating them and taking square of both sides, we get a quadratic equation. This means that the (graphs of the) functions have at most two intersection points.

Now we can use some algebra about quadratic equations and graphs of quadratic polynomials. Note that for all $n\ge 0$ we have $f(n)>0$ and $g(n)\ge 0$, so $f(n)>cg(n)$ iff $(f(n))^2>c^2(g(n))^2$. The function $(f(n))^2-c^2(g(n))^2$ is a quadratic polynomial whose first and third coefficients are positive. This means that the its graph, a parabola, has branches growing up and is positive when $n=0$.

If the equation $(f(n))^2-c^2(g(n))^2=0$ does not have solutions, it means that $f(n)>cg(n)$ for all $n$. (It cannot be that $f(n) for all $n$ because $f(0)>cg(0)$.) If it has one or two solutions, it means that $(f(n))^2-c^2(g(n))^2$ becomes negative at most on a finite segment and then again becomes positive and grows to infinity. So, in any case, $f(n)$ becomes greater that $cg(n)$ for sufficiently large $n$.

Now, we showed that there exist an $n$ such that $f(n)>cg(n)$ and, in fact, $f(m)>cg(m)$ for all $m\ge n$. If this $n then let's take $B$ as $n$; the inequality won't change. I.e., we find $n$ such that $f(n)-cg(n)>0$ everywhere right of $n$, and then we take $\max(n,B)$.