Proving 2n-1<n by Induction: Step by Step Guide

[kathrynag]

Homework Statement

need to prove by induction
2^{n-1}\leqn!

Homework Equations

The Attempt at a Solution

I already did it for P(1) wnat to try P(k) and P(k+1)
P(K):2^{k-1}\leqk!

 

[mutton]

This is straightforward. What's the relationship between 2^k and 2^{k-1}?

 

[kathrynag]

1/22^{k}

 

[mutton]

So plug that into the inequality.

 

[kathrynag]

1/2(2^{k})\leqk!

 

[mutton]

Remember, the goal is to show that 2^k \le (k + 1)!

 

[kathrynag]

I see by plugging in that I would get that, but I don't know why

 

[Fredrik]

What you get is the result that if P(k) holds, then P(k+1) holds too, and we already know that P(1) holds, so...

 

[mutton]

Plugging in what? What you have so far is 2^k \le 2k! So is it true that 2k! \le (k + 1)!? Recall the possible values of k.

 

[kathrynag]

Plugging in what? What you have so far is 2^k \le 2k! So is it true that 2k! \le (k + 1)!? Recall the possible values of k.

(2k)!=(2k)(2k-1)(2k-2)...1

 

[mutton]

2k! is not (2k)!

 

[kathrynag]

2k!=(2k)(2k-2)(2k-4)...2

 

[mutton]

There's no need to expand a factorial every time you see one. Think about the relationship between k! and (k + 1)!

 

[kathrynag]

k! is less than (k+1)!

 

[Gokul43201]

Kathryn,

You need to start from the beginning and write out clearly, step by step, everything till the point you are stuck.

The way the thread is proceeding so far seems to be unhelpful, and a big part of that is in your presentation. The better your effort in showing your work coherently, the better will be the quality of help you receive.

 

[mutton]

k! is less than (k+1)!

By how much?

 

[kathrynag]

Homework Statement

need to prove by induction
2^{n-1}\leqn!

Homework Equations

The Attempt at a Solution

I already did it for P(1) wnat to try P(k) and P(k+1)
P(K):2^{k-1}\leqk!

1/2(2^{k})\leqk!

Plugging in what? What you have so far is 2^k \le 2k! So is it true that 2k! \le (k + 1)!? Recall the possible values of k.

2k!=(2k)(2k-2)(2k-4)...2

k! is less than (k+1)!

k!<(k+1)!
(k+1)!=(k+1)(k)...1
So, by k+1

 

[kathrynag]

Remember, the goal is to show that 2^k \le (k + 1)!

I don't see how we're getting to this.

 

[mutton]

You just showed that (k + 1) k! = (k + 1)!, so

2^k \le 2k! ... (k + 1) k! = (k + 1)!

Fill in the blank by recalling the possible values of k.

 

[kathrynag]

You just showed that (k + 1) k! = (k + 1)!, so

2^k \le 2k! ... (k + 1) k! = (k + 1)!

Fill in the blank by recalling the possible values of k.

Ok so, 2^k<2[(k+1)!/k+1]
2^k<2k!

 

[mutton]

That doesn't connect the left part of what I wrote to the right part.

Think "\le".

 

[kathrynag]

Still unsure...

 

[jmarcian]

ok look at it this way..

PMI= if f(a), where a is some constant, is true for statement, then f(k) is true, from there if f(k+1) is true, the statement it true

F(2) is what? 2^2-1<(2)!, 2¹=1<2=2!
this is true, so it follows that f(k) is true!

then we assume 2^k-1<k!

now we need to prove that f(k+1) is true...

2^(k+1)-1<(k+1)!
simplifying we get,
2^k<(k+1)(k!)
notice here we only factored out a (k+1) from the equation because we can use f(k), which is true, to prove that f(k+1) is true, looky here...
2^k<(k+1)(k!)
from f(k), 2^k-1<k!, but let's just say that it equals that, which it does...
2^k-1=k!
substituting and simplifying...
2^k<(k+1)(2^k-1)
2^k<(k+1)(1/2)(2^k)
2^k<(k/2+1/2)(2^k)

of course now it should be easy to see why it is true...

one thing i distinctly recall from PMI is you need to somehow use f(k) to prove f(k+1), because f(k) is a valid statement it can help you out!



(to mods, sorry for giving out the 'full solution' i know i am not supposed to, but the student seemed to be struggling...)

 

[mutton]

from f(k), 2^k-1<k!, but let's just say that it equals that, which it does...
2^k-1=k!

The equation doesn't hold. Stick with the inequality.

 

[Mark44]

2k!=(2k)(2k-2)(2k-4)...2

No, that's incorrect for two reasons.
2k! = 2*k! = 2(k * (k - 1) * (k - 2) * ... 3 * 2 * 1)
On the other hand, (2k)! = 2k * (2k - 1) * (2k - 2) * ... * 3 * 2 * 1

 

[kathrynag]

No, that's incorrect for two reasons.
2k! = 2*k! = 2(k * (k - 1) * (k - 2) * ... 3 * 2 * 1)
On the other hand, (2k)! = 2k * (2k - 1) * (2k - 2) * ... * 3 * 2 * 1

I don't ge t it. I just multiplied the 2 in.

 

[Mark44]

I don't ge t it. I just multiplied the 2 in.

With 2k! there is just one factor of 2. You can't take one factor of 2 on one side of the equation and have k factors of 2 on the other side.

Look at it with numbers instead of symbols; e.g. with k = 4.
2k! = 2 * 4! = 2*4*3 * 2 * 1 = 48
(2k)! = 8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 40320

Also, 2k! \neq 2 * 4 * 2 * 3 * 2 * 2 * 2 * 1 = 2^4 * 4! = 16 * 24 = 384