Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mathematical Induction problem

  1. Jan 20, 2008 #1
    I am trying to understand induction and not having much luck. Here is my problem as I understand it

    n > or equal to 4, 2^n < n!

    Step 1) Prove it works for n=1 no, n=2 no, n=3 no, n=4 yes 16 < 24

    step 2) assume it works for n=k 2^k < k!

    Step 3) prove it works for n= (k+1)
    2^(k+1) < (k+1)!

    So now I don't know what to do. I am unsure what I am proving. I have successfully figured other problems but not with exponents, inequalities, and factorials.

    Can you give me a push in the right direction?
  2. jcsd
  3. Jan 20, 2008 #2
    Start with 2^(k+1) this is equal to 2*2^k do you understand this step?
    Then you know 2^k<k!, this was your induction hypothesis.
    So then 2^(k+1)<2*k! and you want that to be less than (k+1)! So how can you get (k+1)! form k!? And remember that k>=4.
  4. Jan 20, 2008 #3
    I don't understand how 2^(k+1) is = to 2*2^k
  5. Jan 20, 2008 #4
    How does it become 2*2^k
  6. Jan 20, 2008 #5
    That's basic arithmetic - you're probably just not recognizing it when it's typed this way. How about this:
    Do you know to re-express that in terms of 2 raised to single powers? I'm guessing you do, if you're doing a problem of this level.
  7. Jan 20, 2008 #6
    2*2^k means
    [tex]2\ast2^{k}[/tex] - did you get that?
  8. Jan 20, 2008 #7
    OKay Now I see it. Now you asked How I get (k+1)! form k! I have to admit I have no idea.
  9. Jan 20, 2008 #8
    I think you must be making this harder than it is ... just think of the definition of exponentiation.
    What does the left side of this expression mean, anyway? In words?
  10. Jan 20, 2008 #9
    Left side means 2^k * 2^1 Got it Sorry

    In the last part are you asking me how to get (k+1)! and k! to equal each other?
  11. Jan 20, 2008 #10
    How are (k+1)! and k! related? What is the definition of k!?
  12. Jan 20, 2008 #11
    k! would be k * k+1 * k+2 * k+3 etc. and (k+1)! would be (K+1) * (k+2) * (k+3) etc
  13. Jan 20, 2008 #12
    No, then 1! would be 1*2*3*4*5*6*7*8*9*10*11*12*13*14... which is greater than 1... so obviously that is not the defnition.
  14. Jan 20, 2008 #13
    k! = k(k-1)...2 * 1

    I am really searching here I have been out of school for 35 years. I don't think they taught this stuff back then.
  15. Jan 20, 2008 #14
    ngluth ... where did you think k * k+1 * k+2 * k+3 etc. was going to end?

    n! is defined to be 1 * 2 * 3 * ... * n-1 * n for any positive integer n.
  16. Jan 20, 2008 #15
    BTW ... they certainly did teach this stuff 35 years ago .... that's when I first learned it!! Luckily for me, I've continued to use it in the mean time. I've forgotten much else, though, so I sympathize.
  17. Jan 20, 2008 #16
    Thank you for all your time and patience. Now I can finish the rest of the assignment. This was the hardest one and I just could not understand what they were asking. Thanks
  18. Jan 20, 2008 #17
    I'm sending this again. Don't think it went the first time. Thanks for all your time and patience. I can now finish the assignment. This was the hardest problem. I just could not understand what was going on with it. Thanks. This is an awesome service you are providing. Thanks
  19. Jan 20, 2008 #18
    No problem. Induction is actually quite difficult to grasp at first - many people seem to be unable ever to get it. I've had problems trying to teach it to people who were never able to accept that it was logically sound - they just kept insisting that I'd proved only one case. Oh, well.

    Good luck with the rest of your studies - it sounds like you're turning some cranks that might have gathered a little rust over the years!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook