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!

Proof by Induction

  1. Apr 14, 2013 #1
    1. The problem statement, all variables and given/known data

    Prove 2n ≤ n! for all n ≥ 4.

    2. Relevant equations

    (n+1)! = (n+1)n!

    3. The attempt at a solution

    First, notice P(4): 24 = 16 = 4*4 ≤ 4*6 = 4 * 3 * 2 * 1 = 4!.

    Supposing P(n) is true, check P(n+1):

    2n+1 = 2*2n

    ≤ 2 * n!

    ≤ (n+1)*n!

    = (n+1)!

    Q.E.D.


    I know I'm going wrong in the bold red step as I'm using the very statement I'm trying to prove. I have no idea what to do at this step.
     
  2. jcsd
  3. Apr 14, 2013 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    Actually you wrote "Supposing P(n) is true" which means exactly that [itex]2^n < n![/itex] for this particular n. You don't know it is true for n + 1 as well, that is what you are trying to prove.

    What you have written looks like a valid proof by induction to me. You have shown that it is true for n = 4. Then, assuming it is true for n = 4, you have shown that it holds for n = 5. Assuming it is true for n = 5, it holds for n = 6, etc.
     
  4. Apr 14, 2013 #3
    Hmmm. I would examine the case of n=5, n=6, and so forth, and consider WHY the result you are trying to prove it true. Once you figure that out, you translate it into mathematical language.
     
  5. Apr 14, 2013 #4
    You didn't use what you were trying to prove, you used what some people call the "induction hypothesis" in your proof itself, which is perfectly acceptable, and in many cases, required (often it is what drives us to inductively prove in the first place.)


    HOWEVER, I do understand where your confusion lies. I would like to make the following suggestion to you to avoid this confusion in your proof writing.

    When making your induction hypothesis, don't say "assume P(n) is true." Say: "Assume that for some k in N, P(k) is true."

    This distinguishes between the designation "n" to be "some natural number" in the theoem and k to be "THIS natural number, for which I am assuming my theorem holds."


    First, notice P(4): 24 = 16 = 4*4 ≤ 4*6 = 4 * 3 * 2 * 1 = 4!.

    Suppose that for some k in N, P(k) is holds true. Now, consider the case of n=k+1.

    P(k+1):

    2k+1 = 2*2k

    ≤ 2 * k!

    ≤ (k+1)*k!

    = (k+1)!

    Q.E.D.


    Basically, I'm saying that you should call the number of your induction hypothesis something different. As mathematicians, we should say what we mean and mean what we say, and you are not really assuming that P(n) is true, because that is your theorem.
     
  6. Apr 14, 2013 #5

    This helped clarify the majority of my confusion. Thank you so much!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof by Induction
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...