Results 1 to 9 of 9

Math Help - Help disproving this

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    33

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Selena View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    Posts
    33
    Why is c fixed? Can't c be any positive real number?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Selena View Post
    Why is c fixed? Can't c be any positive real number?
    Any fixed positive real number, yes.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Feb 2010
    Posts
    33
    Quote Originally Posted by emakarov View Post
    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:

    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    I think the solution to the second problem is correct: you choose c and B that work for all n.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Feb 2010
    Posts
    33
    Ah I'm kind of stuck on how to disprove the other one... =/
    Any tips would be greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. disproving a limit.
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: July 19th 2011, 07:30 AM
  2. Replies: 5
    Last Post: March 26th 2011, 10:53 PM
  3. disproving prime numbers
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: October 1st 2008, 06:22 AM
  4. Disproving the completeness of a set of connectives
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 18th 2008, 01:09 PM
  5. Proving and Disproving
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: January 23rd 2008, 09:13 PM

Search Tags


/mathhelpforum @mathhelpforum