-4
$\begingroup$

How would you go about proving $n! < n^n$ using a mathematical induction proof?

I understand how to solve inductive proofs with = but I'm getting a bit lost in this example.

Any help is much appreciated.

$\endgroup$

closed as off-topic by ℋolo, Xander Henderson, Did, Namaste, Adrian Keister Jan 1 at 0:41

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – ℋolo, Xander Henderson, Did, Namaste, Adrian Keister
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ You probably mean either $\leq$ or you want to prove the statement for $n\geq 2$... $\endgroup$ – 5xum Oct 27 '15 at 20:19
  • $\begingroup$ Does one really need induction to see that $n! = 1 \cdot 2 \cdots n \le n \cdot n \cdots n = n^n$ ? $\endgroup$ – lhf Oct 29 '15 at 17:37
  • $\begingroup$ @lhf it's not a question of do you really need t to see that it's true, it's a question of proving it. $\endgroup$ – jknam Oct 29 '15 at 17:48
2
$\begingroup$

First of all, we have $$ 2! < 2^2 $$ which covers the base case. Now, for the induction itself, assume we know that $k!<k^k$ for some $k$. We want to compare $(k+1)!$ and $(k+1)^{k+1}$. Note that $(k+1)! = k!\cdot (k+1)$, which lets us use the induction hypothesis (I.H.): $$ (k+1)! = k!\cdot (k+1) \overset{\text{I.H.}}{<} k^k\cdot(k+1) \overset{k<k+1}{<} (k+1)^k\cdot (k+1) = (k+1)^{k+1} $$ which is what we want.

$\endgroup$
  • $\begingroup$ So in the part where you said $k^k * (k+1) < (k+1)^k*k+1$ why did you not substitute k+1 in the exponent of $(k+1)^k$?That is the part I am confused about $\endgroup$ – jknam Oct 27 '15 at 20:37
  • $\begingroup$ @jknam When I do that transition, I'm really doing the transition $k^k < (k+1)^k$, just with both sides multiplied by $k+1$. While it is true that $k^k < (k+1)^{k+1}$ also, when put into the context of the whole inequality, that would give us $(k+1)! < (k+1)^{k+1}\cdot (k+1) = (k+1)^{k+2}$ which is not what we want. $\endgroup$ – Arthur Oct 27 '15 at 20:52
  • $\begingroup$ Right so how did you determine when you started solving this problem that you wouldn't want to substitute completely? $\endgroup$ – jknam Oct 27 '15 at 21:46
  • $\begingroup$ @jknam A general rule is to substitute as little as possible so that we actually end up with a stronger statement ($(k+1)! < (k+1)^{k+1}$ is stronger than $(k+1)! < (k+1)^{k+2}$) but still be able to get a nice and self-contained result (too many terms to make the inequality closer to equality, and it just becomes uninteresting). In this specific case, I already had $(k+1)^1$, and I wanted to end up with $(k+1)^{k+1}$, which means that I needed whatever else there was to become exactly $(k+1)^k$. Otherwise it wouldn't've matched up to what I wanted in the end. $\endgroup$ – Arthur Oct 27 '15 at 21:54
  • $\begingroup$ I see. So as a rule of thumb, substitute to match the IH? $\endgroup$ – jknam Oct 27 '15 at 21:55
0
$\begingroup$

base case has to be 2 which is evident $$2!=2<2^2=4$$ assume $n!<n^n$, now we have $$(n+1)!=(n+1)n!<(n+1)n^n=n^{n+1}+n^n<n^{n+1}+n^{n+1}=2n^{n+1}<(n+1)^{n+1}$$

$\endgroup$
  • $\begingroup$ So I'm not following where you say $n^(n+1) + n^n < n^(n+1) + n^(n+1)$, where do the n^(n+1) 's on the right side come from? Thanks again for answering my question though, I really appreciate it. $\endgroup$ – jknam Oct 27 '15 at 20:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.