1. Not finding help here? Sign up for a free 30min 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!

Problem 2n-1<n!

  1. Dec 7, 2008 #1
    1. The problem statement, all variables and given/known data
    need to prove by induction
    [tex]2^{n-1}[/tex][tex]\leq[/tex]n!


    2. Relevant equations



    3. The attempt at a solution
    I already did it for P(1) wnat to try P(k) and P(k+1)
    P(K):[tex]2^{k-1}[/tex][tex]\leq[/tex]k!
     
  2. jcsd
  3. Dec 7, 2008 #2
    Re: 2n-1<n!

    This is straightforward. What's the relationship between [tex]2^k[/tex] and [tex]2^{k-1}[/tex]?
     
  4. Dec 7, 2008 #3
    Re: 2n-1<n!

    1/2[tex]2^{k}[/tex]
     
  5. Dec 7, 2008 #4
    Re: 2n-1<n!

    So plug that into the inequality.
     
  6. Dec 7, 2008 #5
    Re: 2n-1<n!

    1/2([tex]2^{k}[/tex])[tex]\leq[/tex]k!
     
  7. Dec 7, 2008 #6
    Re: 2n-1<n!

    Remember, the goal is to show that [tex]2^k \le (k + 1)![/tex]
     
  8. Dec 7, 2008 #7
    Re: 2n-1<n!

    I see by plugging in that I would get that, but I don't know why
     
  9. Dec 7, 2008 #8

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: 2n-1<n!

    What you get is the result that if P(k) holds, then P(k+1) holds too, and we already know that P(1) holds, so...
     
  10. Dec 7, 2008 #9
    Re: 2n-1<n!

    Plugging in what? What you have so far is [tex]2^k \le 2k![/tex] So is it true that [tex]2k! \le (k + 1)![/tex]? Recall the possible values of k.
     
  11. Dec 7, 2008 #10
    Re: 2n-1<n!

    (2k)!=(2k)(2k-1)(2k-2)....1
     
  12. Dec 7, 2008 #11
    Re: 2n-1<n!

    2k! is not (2k)!
     
  13. Dec 7, 2008 #12
    Re: 2n-1<n!

    2k!=(2k)(2k-2)(2k-4)....2
     
  14. Dec 7, 2008 #13
    Re: 2n-1<n!

    There's no need to expand a factorial every time you see one. Think about the relationship between k! and (k + 1)!
     
  15. Dec 7, 2008 #14
    Re: 2n-1<n!

    k! is less than (k+1)!
     
  16. Dec 7, 2008 #15

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: 2n-1<n!

    Kathryn,

    You need to start from the beginning and write out clearly, step by step, everything till the point you are stuck.

    The way the thread is proceeding so far seems to be unhelpful, and a big part of that is in your presentation. The better your effort in showing your work coherently, the better will be the quality of help you receive.
     
  17. Dec 7, 2008 #16
    Re: 2n-1<n!

    By how much?
     
  18. Dec 7, 2008 #17
    Re: 2n-1<n!

    k!<(k+1)!
    (k+1)!=(k+1)(k)...1
    So, by k+1
     
  19. Dec 7, 2008 #18
    Re: 2n-1<n!

    I don't see how we're getting to this.
     
  20. Dec 7, 2008 #19
    Re: 2n-1<n!

    You just showed that (k + 1) k! = (k + 1)!, so

    [tex]2^k \le 2k! .......... (k + 1) k! = (k + 1)![/tex]

    Fill in the blank by recalling the possible values of k.
     
  21. Dec 7, 2008 #20
    Re: 2n-1<n!

    Ok so, 2^k<2[(k+1)!/k+1]
    2^k<2k!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Problem 2n-1<n!
Loading...