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?
The issue is the order of quantifiers in the statement that has to be disproved. The statement says that there exist the same and that work for all .
Here you are saying that for all there exist its own that validates the statement. That would correspond to . However, this is not what is claimed. Since comes before , one has to choose first, and it has to work for all .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
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 has to be replaced by . In this example, we get
So we have to produce a function that, given and will return the required . Let's first leave out the condition and just find such that .
Given and , let's find the points of intersection of and . 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 we have and , so iff . The function 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 .
If the equation does not have solutions, it means that for all . (It cannot be that for all because .) If it has one or two solutions, it means that becomes negative at most on a finite segment and then again becomes positive and grows to infinity. So, in any case, becomes greater that for sufficiently large .
Now, we showed that there exist an such that and, in fact, for all . If this then let's take as ; the inequality won't change. I.e., we find such that everywhere right of , and then we take .