1
$\begingroup$

Prove by induction the inequality: $n! \leq n^n$ for all $n \geq 1$.

I know that the base step is: for $n=1$, $1! \leq 1^1$. The induction hypothesis is: "for all $n \geq 1$ it is true that $n! \leq n^n$". In the induction step I have to prove the inequality $(n+1)! \leq (n+1)^{n+1}$, but I don't know how to prove it.

$\endgroup$

closed as off-topic by Xander Henderson, Brian Borchers, Nick Peterson, José Carlos Santos, user223391 Jan 10 '18 at 6:59

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 improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Xander Henderson, Brian Borchers, Nick Peterson, José Carlos Santos, Community
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Hint : $(n+1)!=(n+1)\cdot n!$ $\endgroup$ – Peter Jan 8 '18 at 21:01
  • 1
    $\begingroup$ Moreover there is an easy proof without induction. For $n\ge 2$, the number $n!$ is the product of the first $n$ numbers which is clearly smaller than the product of $n$ factors $n$, which is $n^n$ $\endgroup$ – Peter Jan 8 '18 at 21:03
3
$\begingroup$

\begin{align*}(n+1)!&=(n+1)\cdot n!\\ &\leq(n+1)\cdot n^n \quad&\text{ (by induction hypothesis)}\\ &\leq (n+1)\cdot(n+1)^n \quad &\text{since } n<n+1\\ &=(n+1)^{n+1} \end{align*}

$\endgroup$
0
$\begingroup$

The induction hypothesis is not

for all $n\ge 1$ it is true that $n!\le n^n$

because this is what you want to prove. The induction step consists in proving

for all $n\ge 1$, if $n!\le n^n$, then $(n+1)!\le(n+1)^{n+1}$

which is quite a different thing. In order to prove this, you can assume that, for a given $n$, you have $n!\le n^n$ (induction hypothesis) and, under this assumption, you have to deduce that $(n+1)!\le(n+1)^{n+1}$.

Now, $$ (n+1)^{n+1}=(n+1)(n+1)^n \ge (n+1)n^n\ge(n+1)n!=(n+1)! $$ The first $\ge$ is because $n+1>n$; the second $\ge$ follows from the induction hypothesis.


You could also work “backwards”. You need to prove that $$ (n+1)^{n+1}-(n+1)!\ge0 $$ which is equivalent to prove that $(n+1)^n\ge n!$, by cancelling $n+1$. This is true because $(n+1)^n\ge n^n$ and $n^n\ge n!$ by the induction hypothesis.

$\endgroup$

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