# Homework Help: Proof by Induction

1. Apr 14, 2013

### mliuzzolino

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. Apr 14, 2013

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

3. Apr 14, 2013

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

4. Apr 14, 2013

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

5. Apr 14, 2013

### mliuzzolino

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