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

Homework Help: Prove by induction (discrete math's)

  1. Nov 4, 2008 #1
    1. The problem statement, all variables and given/known data

    Prove by induction that
    n!> 2^n for n[tex]\geq[/tex]4

    2. Relevant equations

    solved example:
    P(n): 2^n>1+3n let n[tex]\geq[/tex]4
    (base): n=4 2^4=16 > 13=1+12=1+(3)(4)

    (implication): if for n=k: P(k): 2^k>1+3k, for k[tex]\geq[/tex]4

    consider for n=(k+1):

    2^(k+1)=2^k*2^1=2^k(1+1)=2^k+2^k >(1+3k) + (1+3k) for k[tex]\geq[/tex]4
    [tex]\geq[/tex]1+3k+12 > 1+3k+3
    = 1+3(k+1)
    so P(k) => P(k+1)

    3. The attempt at a solution

    (Base) n=k
    P(k): k!>2^k

    (Implication) show P(k)=> P(k+1)

    Consider: n=k+1

    (k+1)! > 2^(k+1)

    (k+1)! = (k+1)k!> (k+1)*2^k

    Please help if you can. I am confused. Thanx.
  2. jcsd
  3. Nov 4, 2008 #2
    assume that the proposition holds for n=k, that is

    [tex] k!>2^k----------------(IH)[/tex] we want to show that it also holds for n=k+1 ?

    [tex] (k+1)!=(k+1)k!=>(IH) (k+1)k!>(k+1)2^k>2*2^k=2^{k+1}[/tex]

    since [tex] k+1>2[/tex] for k>=4.
  4. Nov 5, 2008 #3
    What (IH) means?. I am sorry but English is a second language to me, and I did study most of my math in Europe many years ago.
    I am back to school now.
    Thank you.
    Last edited: Nov 5, 2008
  5. Nov 5, 2008 #4


    User Avatar
    Science Advisor

    "IH" means the "induction hypothesis":that the statement is true for n= k which you then use to show that it is true for n= k+1.

    Also, the "base" case refers to showing that the statement is true for the beginning number, which, here, is n= 4. Is 4!> 24?

    I would NOT start by asserting that "(k+1)! > 2^(k+1)". That is what you want to prove. Better is to start:

    (k+1)!= (k+1)(k!)> (k+1)(2k), where I have used the induction hypothesis: k!> 2k. Can you show that (k+1)(2k is greater than or equal to 2k+1? Remember that k is at least 4.
  6. Nov 5, 2008 #5
    I am sorry, thanks for the note. I know that I have to start first with the proof in base part, I just skip it in a hurry. :redface:

    Here is: let n=4

    (base) n=k

    consider for n=k+1

    (k+1)!= (k+1)k!>(k+1)(2^k)

    I don't know how to show it. Please help. Can you show that (k+1)(2k is greater than or equal to 2k+1? Remember that k is at least 4.
    Last edited: Nov 5, 2008
  7. Nov 6, 2008 #6


    User Avatar
    Science Advisor

    Could you show that 3(2k)> 2k+1?

    How large is k+1?
  8. Nov 6, 2008 #7
    I am not sure , but I will try.
    6^k > 2^k*2

    I don't think I can finish this problem. I asked in class similar problem ,but this professor is happy to make us more confused, he doesn't explain well at all. I also don't think that other kids in the class get it. I just don't get it, sorry.
    Last edited: Nov 6, 2008
  9. Nov 6, 2008 #8
    How large is k+1?
    Then what?
  10. Nov 7, 2008 #9


    User Avatar
    Science Advisor

    Well, the important thing is to be able to blame your professor isn't it? That way you don't have to take responsibility for your own education.

    Who are you going to blame for the fact that you think 3*2k is equal to 6k?
  11. Nov 7, 2008 #10
    Didn't you make a mistake under presure or in a hurry to get many thinks done. I mention that I am almost 50 years old and I am back to school.
    I it is diffucult for me. I can get this problem done even with out your help.

    I don't blame anybody. But similar example was given and you have no idea what kind of people are teaching around the country. Excusme, but a good mathematicians don't make good teachers.

    I was confised from the different form given in the example.
    Thank you anyway. Please forget about this problem and delete it.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook