# proof by mathematical induction (n)!< (n)^n

"Let P(n) be the statement that (n)! < (n)^n, where is an integer greater than 1. Prove by mathematical induction that P(n) is true for all integers n greater than 1."

I've written

Basic step

Show that P(2) is true:

2! < (2)^2

1*2 < 2*2

2 < 4 (which is true)

Thus we've proven that the first step is true.

Inductive hypothesis

Assume P(k) => ((k)! < (k)^k ) is true

Inductive step

Show that P(k+1) is true:

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

1*2*3*...(k)(k+1) < (k+1)(k+1)(k+1)...(k+1)

1*2*3*...(k^2 + k ) < (k+1)(k+1)(k+1)...*(k+1)

I'm not sure on how to continue from here...

• Use the assumption that $P(k)$ is true – J. W. Tanner May 16 at 17:59
• Too many parentheses! $(n)!$ is just $n!$, $(n)^n$ is just $n^n$... – TonyK May 16 at 18:00
• Hint: $n!<n^n\iff (n-1)!<n^{n-1}$. – lulu May 16 at 19:21

## 2 Answers

Start with $$P(k)$$.

$$k! < k^k$$

We want to show this implies $$P(k+1)$$. Perhaps multiplying both sides by $$k+1$$ will lead us closer to $$P(k+1)$$.

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

Can you obtain $$P(k+1)$$ from here?

$$(k+1)^{k+1} = (k+1)\cdot(k+1)^{k} > (k+1)\cdot k^k>(k+1)\cdot k! = (k+1)!$$