Is This Mathematical Induction Proof Correct for Factorials and Exponents?

[nastygoalie89]

Homework Statement

For all integers n=>1, n! <= n^n

Homework Equations

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?

 

[vela]

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

 

[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?

 

[vela]

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

(k+1) k! ≤ (k+1) k^k

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

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

 

[D H]

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!<=k^k is assumed to be true.

 

[nastygoalie89]

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

 

[D H]

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

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

 

[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 I am begging the question at step 3 here

 

[D H]

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

 

[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

 

[vela]

3. (k+1)k^k <= (k+1)^(k+1) multiply by k to get (k+1)k^(k+1)<=(k+1)k^(k+1)

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

 

[nastygoalie89]

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

 

[vela]

Start with k ≤ k+1, which is obviously true.

 

[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)

 

[vela]

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)

This would give you k(k+1)^k ≤ (k+1)^k+1, not (k+1)k^k < (k+1)^k+1.

 

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

 

[vela]

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.

 

[nastygoalie89]

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

 

[vela]

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

That's not really the point. You've gotten to k!(k+1)≤(k+1)k^k 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)k^k. 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 k^k(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) k^k ≤ (k+1) (k+1)^k.

 

[nastygoalie89]

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