How Do You Prove \(2^{k+1} < (k+1)!\) Using Induction?

Click For Summary

Discussion Overview

The discussion revolves around proving the inequality \(2^{k+1} < (k+1)!\) using mathematical induction, specifically for \(n \geq 4\). Participants explore the steps of induction, including establishing a base case, formulating an induction hypothesis, and attempting to prove the case for \(n = k+1\).

Discussion Character

  • Exploratory
  • Technical explanation
  • Homework-related

Main Points Raised

  • One participant expresses confusion about the induction process and the specific inequality to prove.
  • Another participant clarifies that \(2^{k+1}\) can be rewritten as \(2 \cdot 2^k\) and suggests using the induction hypothesis \(2^k < k!\) to progress.
  • Several participants seek clarification on the arithmetic behind \(2^{k+1} = 2 \cdot 2^k\), indicating a lack of familiarity with exponentiation rules.
  • There is a discussion about the relationship between \(k!\) and \((k+1)!\), with participants attempting to articulate the definitions of factorials.
  • One participant reflects on their long absence from formal education and expresses difficulty in grasping the concepts being discussed.
  • Another participant shares their own experience with learning induction and acknowledges the challenges faced by others in understanding it.

Areas of Agreement / Disagreement

Participants generally express confusion and seek clarification on various aspects of the problem, indicating that there is no consensus on how to proceed with the proof. Multiple viewpoints and levels of understanding are present throughout the discussion.

Contextual Notes

Some participants exhibit uncertainty about basic arithmetic and factorial definitions, which may affect their ability to engage with the problem effectively. The discussion reflects varying levels of familiarity with mathematical induction and related concepts.

Who May Find This Useful

This discussion may be useful for individuals learning about mathematical induction, particularly those struggling with the concepts of exponentiation and factorials, as well as those revisiting these topics after a long absence from formal education.

ngluth
Messages
14
Reaction score
0
I am trying to understand induction and not having much luck. Here is my problem as I understand it

Problem:
n > or equal to 4, 2^n < n!

Step 1) Prove it works for n=1 no, n=2 no, n=3 no, n=4 yes 16 < 24

step 2) assume it works for n=k 2^k < k!

Step 3) prove it works for n= (k+1)
2^(k+1) < (k+1)!

So now I don't know what to do. I am unsure what I am proving. I have successfully figured other problems but not with exponents, inequalities, and factorials.

Can you give me a push in the right direction?
 
Physics news on Phys.org
Start with 2^(k+1) this is equal to 2*2^k do you understand this step?
Then you know 2^k<k!, this was your induction hypothesis.
So then 2^(k+1)<2*k! and you want that to be less than (k+1)! So how can you get (k+1)! form k!? And remember that k>=4.
 
I don't understand how 2^(k+1) is = to 2*2^k
 
How does it become 2*2^k
 
ngluth said:
I don't understand how 2^(k+1) is = to 2*2^k
That's basic arithmetic - you're probably just not recognizing it when it's typed this way. How about this:
[tex]2^{k+1}[/tex]
Do you know to re-express that in terms of 2 raised to single powers? I'm guessing you do, if you're doing a problem of this level.
 
2*2^k means
[tex]2\ast2^{k}[/tex] - did you get that?
 
OKay Now I see it. Now you asked How I get (k+1)! form k! I have to admit I have no idea.
 
ngluth said:
OKay Now I see it. Now you asked How I get (k+1)! form k! I have to admit I have no idea.
I think you must be making this harder than it is ... just think of the definition of exponentiation.
[tex]2^{k+1}=2\ast2^{k}[/tex]
What does the left side of this expression mean, anyway? In words?
 
Left side means 2^k * 2^1 Got it Sorry In the last part are you asking me how to get (k+1)! and k! to equal each other?
 
  • #10
How are (k+1)! and k! related? What is the definition of k!?
 
  • #11
k! would be k * k+1 * k+2 * k+3 etc. and (k+1)! would be (K+1) * (k+2) * (k+3) etc
 
  • #12
ngluth said:
k! would be k * k+1 * k+2 * k+3 etc. and (k+1)! would be (K+1) * (k+2) * (k+3) etc

No, then 1! would be 1*2*3*4*5*6*7*8*9*10*11*12*13*14... which is greater than 1... so obviously that is not the defnition.
 
  • #13
k! = k(k-1)...2 * 1

I am really searching here I have been out of school for 35 years. I don't think they taught this stuff back then.
 
  • #14
ngluth ... where did you think k * k+1 * k+2 * k+3 etc. was going to end?

n! is defined to be 1 * 2 * 3 * ... * n-1 * n for any positive integer n.
 
  • #15
BTW ... they certainly did teach this stuff 35 years ago ... that's when I first learned it! Luckily for me, I've continued to use it in the mean time. I've forgotten much else, though, so I sympathize.
 
  • #16
Thank you for all your time and patience. Now I can finish the rest of the assignment. This was the hardest one and I just could not understand what they were asking. Thanks
 
  • #17
I'm sending this again. Don't think it went the first time. Thanks for all your time and patience. I can now finish the assignment. This was the hardest problem. I just could not understand what was going on with it. Thanks. This is an awesome service you are providing. Thanks
 
  • #18
No problem. Induction is actually quite difficult to grasp at first - many people seem to be unable ever to get it. I've had problems trying to teach it to people who were never able to accept that it was logically sound - they just kept insisting that I'd proved only one case. Oh, well.

Good luck with the rest of your studies - it sounds like you're turning some cranks that might have gathered a little rust over the years!
 

Similar threads

  • · Replies 4 ·
Replies
4
Views
3K
  • · Replies 11 ·
Replies
11
Views
4K
  • · Replies 10 ·
Replies
10
Views
4K
  • · Replies 10 ·
Replies
10
Views
3K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 19 ·
Replies
19
Views
4K
  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 3 ·
Replies
3
Views
6K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 6 ·
Replies
6
Views
7K