# Homework Help: Problem 2n-1<n!

1. Dec 7, 2008

### kathrynag

1. The problem statement, all variables and given/known data
need to prove by induction
$$2^{n-1}$$$$\leq$$n!

2. Relevant equations

3. 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}$$$$\leq$$k!

2. Dec 7, 2008

### mutton

Re: 2n-1<n!

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

3. Dec 7, 2008

### kathrynag

Re: 2n-1<n!

1/2$$2^{k}$$

4. Dec 7, 2008

### mutton

Re: 2n-1<n!

So plug that into the inequality.

5. Dec 7, 2008

### kathrynag

Re: 2n-1<n!

1/2($$2^{k}$$)$$\leq$$k!

6. Dec 7, 2008

### mutton

Re: 2n-1<n!

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

7. Dec 7, 2008

### kathrynag

Re: 2n-1<n!

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

8. Dec 7, 2008

### Fredrik

Staff Emeritus
Re: 2n-1<n!

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

9. Dec 7, 2008

### mutton

Re: 2n-1<n!

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.

10. Dec 7, 2008

### kathrynag

Re: 2n-1<n!

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

11. Dec 7, 2008

### mutton

Re: 2n-1<n!

2k! is not (2k)!

12. Dec 7, 2008

### kathrynag

Re: 2n-1<n!

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

13. Dec 7, 2008

### mutton

Re: 2n-1<n!

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

14. Dec 7, 2008

### kathrynag

Re: 2n-1<n!

k! is less than (k+1)!

15. Dec 7, 2008

### Gokul43201

Staff Emeritus
Re: 2n-1<n!

Kathryn,

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

16. Dec 7, 2008

### mutton

Re: 2n-1<n!

By how much?

17. Dec 7, 2008

### kathrynag

Re: 2n-1<n!

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

18. Dec 7, 2008

### kathrynag

Re: 2n-1<n!

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

19. Dec 7, 2008

### mutton

Re: 2n-1<n!

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.

20. Dec 7, 2008

### kathrynag

Re: 2n-1<n!

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