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!

Mathematical Induction

  1. Jan 10, 2006 #1
    I have a problem when trying to prove n! >= 2^(n-1).

    My work:

    Assuming n=k, k! >= 2^k-1 (induction hypothesis).

    To prove true for n=k+1,

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

    Now considering R.S., 2^k = (2^(k-1))(2)


    I get stuck here. I don't know how to continue onwards to prove that (k+1)! is >= 2^k.

    Can anyone show what I did wrong or what I should've done?
     
    Last edited: Jan 11, 2006
  2. jcsd
  3. Jan 10, 2006 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    First, You don't mean 2^k-1, you mean 2^(k-1). That is, the formula you want to prove is n!>= 2k-1, not n!>= 2k-1 (which is not true, for example, for n= 3).

    Second, you didn't do the "base case": when n= 1, n!= 1 which is equal to 21-1= 2-1.

    Third, assuming that k!>= 2^(k- 1), you don't know that (k+1)! >= 2^((k+1)-1)= 2^k . That's what you want to prove!

    (k+1)!= (k+1)k! >= (k+1)(2k-1). Now what you need is to prove that (k+1)(2k-1) is larger than or equal to 2k. Perhaps you can do that with a separate induction proof.
     
  4. Jan 11, 2006 #3
    k! >= 2^(k-1)
    (k+1)k! >= (k+1)2^(k-1)
    (k+1)! >= (k+1)2^(k-1)

    You want a 2^k to appear on the RHS. You know that k is a natural number. It should be fairly easy to finish it off from there.
     
  5. Jan 11, 2006 #4
    Alright, thanks guys. I got it.
     
  6. Jan 11, 2006 #5

    benorin

    User Avatar
    Homework Helper

    There's a simple way to do it without induction:

    [tex]n!\geq 2^{n-1}\Rightarrow \ln (n!) = \sum_{k=1}^{n} \ln (k) \geq (n-1)\ln (2)[/tex]

    since [itex] \ln(1)=0[/itex] and [itex] \ln(1)<\ln(2)<\ln(3)<\cdot\cdot\cdot<\ln(n-1)<\ln(n)[/itex] it follows that

    [tex]\sum_{k=1}^{n} \ln (k) = \sum_{k=2}^{n} \ln (k) > \sum_{k=2}^{n} \ln (2) \geq (n-1)\ln (2)[/tex]

    where the last inequality is not an equality for the sake of the n=1 case.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Mathematical Induction
  1. Mathematical induction (Replies: 24)

  2. Mathematical Induction (Replies: 3)

  3. Mathematical Induction (Replies: 15)

  4. Mathematical induction (Replies: 0)

Loading...