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

[ngluth]

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?

 

[d_leet]

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.

 

[ngluth]

I don't understand how 2^(k+1) is = to 2*2^k

 

[ngluth]

How does it become 2*2^k

 

[belliott4488]

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:
$$2^{k+1}$$
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.

 

[belliott4488]

2*2^k means
$$2\ast2^{k}$$ - did you get that?

 

[ngluth]

OKay Now I see it. Now you asked How I get (k+1)! form k! I have to admit I have no idea.

 

[belliott4488]

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.
$$2^{k+1}=2\ast2^{k}$$
What does the left side of this expression mean, anyway? In words?

 

[ngluth]

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?

 

[d_leet]

How are (k+1)! and k! related? What is the definition of k!?

 

[ngluth]

k! would be k * k+1 * k+2 * k+3 etc. and (k+1)! would be (K+1) * (k+2) * (k+3) etc

 

[d_leet]

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.

 

[ngluth]

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.

 

[belliott4488]

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.

 

[belliott4488]

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.

 

[ngluth]

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

 

[ngluth]

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

 

[belliott4488]

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!