# Am I begging the question?

1. May 9, 2010

### nastygoalie89

1. The problem statement, all variables and given/known data
For all integers n=>1, n! <= n^n

2. Relevant equations

3. The attempt at a solution
Let p(n) be the inequality n! <= n^n, for all integers n=>1.
Base case: p(1) = 1! <=1^1 1<=1 check
IHOP: Assume p(k), that is assume k!<=k^k for some integer k.
Show p(k+1): show (k+1)! <= (k+1)^(k+1)
It can be rewritten as k!(k+1) <= (k+1)^k (k+1)
divide both sides by (k+1)
which leaves k! <= (k+1)^k

Is this correct or so I beg the question/ mess up my simple math?

2. May 9, 2010

### vela

Staff Emeritus
Logically, it's a bit muddled. You're starting with what you want to prove and showing it leads to a true statement and therefore concluding what you started with is true. That's not logically correct. What you want to do is start with known true statements and show that what you're trying to prove follows. In other words, you want to show p implies q, but what you did was show q implies p.

Start with (k+1)! = k! (k+1). Use the induction hypothesis and manipulate the RHS a bit more to show it's less than (k+1)(k+1).

3. May 9, 2010

### nastygoalie89

so it would be: k!<=k^k
multiply by (k+1) on both sides
(k+1)! = k!(k+1)<= (k+1)^k (k+1)
since k is an integer k+1 is an integer
am I closer?

4. May 9, 2010

### vela

Staff Emeritus
You have the induction hypothesis, k! ≤ kk, which you assume is true with k≥1. Then it follows that

(k+1) k! ≤ (k+1) kk

from the normal rule about multiplying an inequality by a positive quantity, k+1.

Now show that (k+1) kk is less than or equal to (k+1)k+1. Try starting with the fact that k ≤ k+1.

5. May 9, 2010

### D H

Staff Emeritus
He's almost there in post #1. Just a bit loose, and the final step doesn't say anything (yet). All that is needed is to show that k!<=(k+1)k is a true statement given the assumption. This is quite trivial given that k!<=kk is assumed to be true.

6. May 9, 2010

### nastygoalie89

how do you get (k+1) k^k? isn't it (k+1)(k+1)^k?

7. May 9, 2010

### D H

Staff Emeritus
Nope. Vela is right. You need to assume that k!≤kk. You cannot jump from that to (k+1)!≤(k+1)k+1. What is valid is to jump from k!≤kk to (k+1)k!≤(k+1)kk. What can you say about (k+1)kk compared to (k+1)k+1?

Hint: if a≤b and b≤c then a≤c.

8. May 9, 2010

### nastygoalie89

1. k!< k^k
2. multiply by (k+1) to get k!(k+1) < (k+1)k^k
3. k!(k+1) < (k+1)k^k < (k+1)^(k+1)
4. therefore, k!(k+1) < (k+1)^(k+1)
I feel im begging the question at step 3 here

9. May 9, 2010

### D H

Staff Emeritus
Much closer, actually. What justifies step 3? You have two parts, (k+1)k!<(k+1)kk and (k+1)kk<(k+1)k+1. Prove each of those.

10. May 9, 2010

### nastygoalie89

1. k!< k^k
2. multiply by (k+1) to get k!(k+1) <= (k+1)k^k
3. (k+1)k^k <= (k+1)^(k+1) multiply by k to get (k+1)k^(k+1)<=(k+1)k^(k+1)
therefore, k!(k+1) <= (k+1)k^(k+1), divide by (k+1)
k! <= (k+1)^k

11. May 9, 2010

### vela

Staff Emeritus
You don't want to start with (k+1)kk ≤ (k+1)k+1; that's what you want to prove.

12. May 9, 2010

### nastygoalie89

ah i have no idea how to prove that without starting with 'q'

13. May 9, 2010

### vela

Staff Emeritus

14. May 9, 2010

### nastygoalie89

i think i have it.
k! < k^k, multiply by (k+1)
k!(k+1)= (k+1)! < (k+1)k^k
and since k<= k+1, multiply by (k+1)^k
this gives us (k+1)k^k < (k+1)^(k+1)
we proved (k+1)! < (k+1)k^k < (k+1)^(k+1)
therefore, (k+1)! < (k+1)^(k+1)

15. May 9, 2010

### vela

Staff Emeritus
This would give you k(k+1)k ≤ (k+1)k+1, not (k+1)kk < (k+1)k+1.

16. May 9, 2010

### Matterwave

I'm pretty sure you were there in the first post. All you had to then say was that k!<(k+1)^k because k!<k^k<(k+1)^k. k^k is an increasing function for all k>1.

17. May 9, 2010

### vela

Staff Emeritus
No, the first post isn't correct. A lot of students write a "proof" like that, and some graders let it slide in introductory classes, but it's wrong. It's close. Most of the pieces are there, but they have to be arranged in the right way to make a correct proof.

18. May 11, 2010

### nastygoalie89

how do I get to k(k+1)k ≤ (k+1)k+1 from k<k+1, without multiplying (k+1)^k?

19. May 11, 2010

### vela

Staff Emeritus
That's not really the point. You've gotten to k!(k+1)≤(k+1)kk in your proof, and you can certainly multiply k≤k+1 by (k+1)k to get k(k+1)k≤(k+1)k+1. The problem is, that doesn't help you because you don't know how k(k+1)k compares to (k+1)kk. To put it in simpler terms, it's like you know a<b and c<d. Without knowing how b and c compare, you can't conclude a<d.

What you want to do is turn the lefthand side of k≤k+1 into kk(k+1) and, by doing the same things to the righthand side, turn it into (k+1)k+1. Let me write it even more suggestively. You want to go from

k ≤ k+1

to

(k+1) kk ≤ (k+1) (k+1)k.

20. May 11, 2010

### nastygoalie89

I just don't see how to get from k to (k+1)k^k