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
    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook




Loading...
Similar Threads for Mathematical Induction Date
Hard mathematical induction question Nov 19, 2011
Mathematical induction Mar 9, 2010
Mathematical Induction Jul 10, 2008
Mathematical induction Jul 3, 2008
Mathematical Induction Jun 17, 2008