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

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

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)!$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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