Help disproving this

Printable View

March 12th 2010, 06:44 PM
Selena

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:

http://imgur.com/SYPzV.jpg

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.
March 12th 2010, 06:59 PM
Drexel28

Quote:

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:

http://imgur.com/SYPzV.jpg

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.
March 12th 2010, 07:18 PM
Selena

Why is c fixed? Can't c be any positive real number?
March 12th 2010, 08:10 PM
Drexel28

Quote:

Originally Posted by Selena

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

Any fixed positive real number, yes.
March 13th 2010, 02:07 AM
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$ .

Quote:

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$ .
March 13th 2010, 11:28 AM
Selena

Quote:

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?

http://imgur.com/8cBSM.jpg

(Oops ignore the "|" after the N)

This is what I have for it so far:

http://imgur.com/yqvDK.jpg
March 13th 2010, 11:47 AM
emakarov

I think the solution to the second problem is correct: you choose c and B that work for all n.
March 13th 2010, 03:28 PM
Selena

Ah I'm kind of stuck on how to disprove the other one... =/
Any tips would be greatly appreciated.
March 14th 2010, 09:59 AM
emakarov

Quote:

http://imgur.com/SYPzV.jpg

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},\,<br /> \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)<cg(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<B$ 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)$ .