Proof by Induction: 2n ≤ n! for All n ≥ 4

[mliuzzolino]

Homework Statement

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

Homework Equations

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

The Attempt at a Solution

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

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

2ⁿ⁺¹ = 2*2ⁿ

≤ 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.

 

[CompuChip]

Actually you wrote "Supposing P(n) is true" which means exactly that 2^n < n! 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.

 

[ImaLooser]

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.

 

[1MileCrash]

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.

 

[mliuzzolino]

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.

This helped clarify the majority of my confusion. Thank you so much!