1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Am I begging the question?

  1. May 9, 2010 #1
    1. The problem statement, all variables and given/known data
    For all integers n=>1, n! <= n^n


    2. Relevant equations



    3. The attempt at a solution
    Let p(n) be the inequality n! <= n^n, for all integers n=>1.
    Base case: p(1) = 1! <=1^1 1<=1 check
    IHOP: Assume p(k), that is assume k!<=k^k for some integer k.
    Show p(k+1): show (k+1)! <= (k+1)^(k+1)
    It can be rewritten as k!(k+1) <= (k+1)^k (k+1)
    divide both sides by (k+1)
    which leaves k! <= (k+1)^k


    Is this correct or so I beg the question/ mess up my simple math?
     
  2. jcsd
  3. May 9, 2010 #2

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Logically, it's a bit muddled. You're starting with what you want to prove and showing it leads to a true statement and therefore concluding what you started with is true. That's not logically correct. What you want to do is start with known true statements and show that what you're trying to prove follows. In other words, you want to show p implies q, but what you did was show q implies p.

    Start with (k+1)! = k! (k+1). Use the induction hypothesis and manipulate the RHS a bit more to show it's less than (k+1)(k+1).
     
  4. May 9, 2010 #3
    so it would be: k!<=k^k
    multiply by (k+1) on both sides
    (k+1)! = k!(k+1)<= (k+1)^k (k+1)
    since k is an integer k+1 is an integer
    am I closer?
     
  5. May 9, 2010 #4

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    You have the induction hypothesis, k! ≤ kk, which you assume is true with k≥1. Then it follows that

    (k+1) k! ≤ (k+1) kk

    from the normal rule about multiplying an inequality by a positive quantity, k+1.

    Now show that (k+1) kk is less than or equal to (k+1)k+1. Try starting with the fact that k ≤ k+1.
     
  6. May 9, 2010 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    He's almost there in post #1. Just a bit loose, and the final step doesn't say anything (yet). All that is needed is to show that k!<=(k+1)k is a true statement given the assumption. This is quite trivial given that k!<=kk is assumed to be true.
     
  7. May 9, 2010 #6
    how do you get (k+1) k^k? isn't it (k+1)(k+1)^k?
     
  8. May 9, 2010 #7

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Nope. Vela is right. You need to assume that k!≤kk. You cannot jump from that to (k+1)!≤(k+1)k+1. What is valid is to jump from k!≤kk to (k+1)k!≤(k+1)kk. What can you say about (k+1)kk compared to (k+1)k+1?

    Hint: if a≤b and b≤c then a≤c.
     
  9. May 9, 2010 #8
    1. k!< k^k
    2. multiply by (k+1) to get k!(k+1) < (k+1)k^k
    3. k!(k+1) < (k+1)k^k < (k+1)^(k+1)
    4. therefore, k!(k+1) < (k+1)^(k+1)
    I feel im begging the question at step 3 here
     
  10. May 9, 2010 #9

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Much closer, actually. What justifies step 3? You have two parts, (k+1)k!<(k+1)kk and (k+1)kk<(k+1)k+1. Prove each of those.
     
  11. May 9, 2010 #10
    1. k!< k^k
    2. multiply by (k+1) to get k!(k+1) <= (k+1)k^k
    3. (k+1)k^k <= (k+1)^(k+1) multiply by k to get (k+1)k^(k+1)<=(k+1)k^(k+1)
    therefore, k!(k+1) <= (k+1)k^(k+1), divide by (k+1)
    k! <= (k+1)^k
     
  12. May 9, 2010 #11

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    You don't want to start with (k+1)kk ≤ (k+1)k+1; that's what you want to prove.
     
  13. May 9, 2010 #12
    ah i have no idea how to prove that without starting with 'q'
     
  14. May 9, 2010 #13

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Start with k ≤ k+1, which is obviously true.
     
  15. May 9, 2010 #14
    i think i have it.
    k! < k^k, multiply by (k+1)
    k!(k+1)= (k+1)! < (k+1)k^k
    and since k<= k+1, multiply by (k+1)^k
    this gives us (k+1)k^k < (k+1)^(k+1)
    we proved (k+1)! < (k+1)k^k < (k+1)^(k+1)
    therefore, (k+1)! < (k+1)^(k+1)
     
  16. May 9, 2010 #15

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    This would give you k(k+1)k ≤ (k+1)k+1, not (k+1)kk < (k+1)k+1.
     
  17. May 9, 2010 #16

    Matterwave

    User Avatar
    Science Advisor
    Gold Member

    I'm pretty sure you were there in the first post. All you had to then say was that k!<(k+1)^k because k!<k^k<(k+1)^k. k^k is an increasing function for all k>1.
     
  18. May 9, 2010 #17

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    No, the first post isn't correct. A lot of students write a "proof" like that, and some graders let it slide in introductory classes, but it's wrong. It's close. Most of the pieces are there, but they have to be arranged in the right way to make a correct proof.
     
  19. May 11, 2010 #18
    how do I get to k(k+1)k ≤ (k+1)k+1 from k<k+1, without multiplying (k+1)^k?
     
  20. May 11, 2010 #19

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    That's not really the point. You've gotten to k!(k+1)≤(k+1)kk in your proof, and you can certainly multiply k≤k+1 by (k+1)k to get k(k+1)k≤(k+1)k+1. The problem is, that doesn't help you because you don't know how k(k+1)k compares to (k+1)kk. To put it in simpler terms, it's like you know a<b and c<d. Without knowing how b and c compare, you can't conclude a<d.

    What you want to do is turn the lefthand side of k≤k+1 into kk(k+1) and, by doing the same things to the righthand side, turn it into (k+1)k+1. Let me write it even more suggestively. You want to go from

    k ≤ k+1

    to

    (k+1) kk ≤ (k+1) (k+1)k.
     
  21. May 11, 2010 #20
    I just don't see how to get from k to (k+1)k^k
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Am I begging the question?
Loading...