Proof by Induction

  • #1

Homework Statement



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

Homework Equations



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

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.
 

Answers and Replies

  • #2
CompuChip
Science Advisor
Homework Helper
4,306
48
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.
 
  • #3
487
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.
 
  • #4
1,335
41
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
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!
 

Related Threads on Proof by Induction

  • Last Post
Replies
6
Views
883
  • Last Post
Replies
4
Views
887
  • Last Post
Replies
5
Views
961
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
1
Views
944
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
2
Views
779
  • Last Post
Replies
2
Views
766
  • Last Post
Replies
12
Views
2K
Top