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


    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


    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