# Use mathematical induction to prove the following $n! < n^n$

So I'm reviewing some problems but I can't seem to understand the part below, doesn't really have to do with induction but just so you guys understand whats going on.

Use mathematical induction to prove the following statement is true for integers $n > 1:$

$n! < n^n$

Solution

Base Case: $n = 2$

LHS: $2! = 2$

RHS: $2^2 = 4$

Because the LHS is less than the RHS the base case is shown to be true.

Inductive Hypothesis: Assume for an arbitrary positive integer $n = k$ s.t $k! < k^k$

Inductive Step: Prove for $n = k+1$ that $(k+1)! < (k+1)^{k+1}$

(starting with the IH)

$k! < k^k$

$(k+1)k! < (k+1)k^k$

$(k+1)! < (k+1)k^k$ <--

$(k+1)! < (k+1)(k+1)^k$ <--

$(k+1)! < (k+1)^{k+1}$

(starting with k+1)

(k+1)! = (k+1)k!

$(k+1)! < (k+1)k^k$ by the IH

$(k+1)! < (k+1)(k+1)^k$

$(k+1)! < (k+1)^{k+1}$

Now what I'm lost on is how did he go from $(k+1)k^k$ to $(k+1)(k+1)^k$ ?

• The solution is just indicating that if the LHS is less than $(k+1)k^k$, then it is also less than $(k+1)(k+1)^k$. – Marcus Andrews Dec 3 '15 at 19:46
• This might be a duplicate of this question. – mickep Dec 3 '15 at 20:08

In this case, both sides were not equally operated on, but instead the property "$a<b$ and $b<c$ implies $a<c$" was used.
In one of the lines you have $(k+1)! < (k+1)k^k.$
As a tangential fact, we know $(k+1)k^k < (k+1)^{k+1},\;$ since $\;(k+1)k^k < (k+1)(k+1)^k$.
From these two inequalities, it follows that $(k+1)! < (k+1)^{k+1},$ which is the next line in your proof.
• Ahhhhh, now I see it. So $c$ is just a function he picked that is greater than $a$ and $b$ but also something that I can manipulate to finish the proof? – RiGid Dec 3 '15 at 20:24
In the second part, you can use the fact that $(k+1)^{k+1}=\sum_{i=0}^{k+1}\binom{k+1}{i}k^i=1+\binom{k+1}{2}k+...+\underset{=(k+1)}{\underbrace{\binom{k+1}{k}}}k^k+k^{k+1}>(k+1)k^k$ and so $$(k+1)!=(k+1)k!\underset{\text{@Marcus Andrews indication}}{<}(k+1)k^k<(k+1)^{k+1}.$$