4
$\begingroup$

So I'm trying to prove, by induction, that $$ n^n \geq n!, \forall n\geq1$$

Base case:

$$ \text{For } n=1, 1^1 = 1 \geq 1 = 1!$$

Hypothesis:

$$ n^n \geq n!$$

Step:

$$ \text{Trying to prove: } n^{n+1} \geq (n+1)! $$

Now, somewhere around here I get some contradicting things. For example, if I start from the right side I get:

$$ (n+1)! = (n+1)\cdot n! \leq (n+1)\cdot n^n = n\cdot n^n + n^n = n^{n+1} + n^n$$

Based on this I would need $n^{n+1} + n^n$ to be less than or equal to $n^{n+1}$, which is certainly not true. Something similar happens when I go the other way.

Any ideas what I'm doing wrong here? Thanks.

$\endgroup$
7
  • 4
    $\begingroup$ "Trying to prove: $n^{n+1} \geq (n+1)!$" No: Trying to prove: $(n+1)^{n+1} \geq (n+1)!$ $\endgroup$
    – Did
    Dec 14 '18 at 12:29
  • 1
    $\begingroup$ Well, now I feel stupid. Thanks. $\endgroup$
    – Koy
    Dec 14 '18 at 12:30
  • 3
    $\begingroup$ Do you have to prove this with induction? I think you could just write out what the two terms mean, and you will see that the hypothesis is true. $\endgroup$
    – Matti P.
    Dec 14 '18 at 12:30
  • $\begingroup$ Indeed induction is not at all the most direct route here. $\endgroup$
    – Did
    Dec 14 '18 at 12:31
  • 6
    $\begingroup$ "Well, now I feel stupid." Who never does? "Thanks." You are welcome. $\endgroup$
    – Did
    Dec 14 '18 at 12:31
4
$\begingroup$

$(n+1)! = (n+1)\cdot n! \leq (n+1)\cdot n^n$ by induction hypothesis, and $(n+1)\cdot n^n\leq (n+1)\cdot (n+1)^n = (n+1)^{n+1}$. Done.

$\endgroup$
1
  • $\begingroup$ I don't know why, but your answer shows"$\leq (n+1) by \cdot n^n$" even though you did not type it that way. $\endgroup$ Dec 14 '18 at 15:40
7
$\begingroup$

You should try to prove that $$(n+1)^{n+1} \ge (n+1)!$$

\begin{align} (n+1)^{n+1} &= (n+1) (n+1)^n\\ &\ge(n+1)n^n \end{align}

Now use induction hypothesis.

$\endgroup$
5
$\begingroup$

You are trying to prove :

$$(n+1)^{n+1} \geq (n+1)!$$

Not :

$$n^{n+1} \geq (n+1)!$$

$\endgroup$
2
  • $\begingroup$ This isn't an answer! Can you show some steps ? $\endgroup$ Dec 14 '18 at 12:32
  • 4
    $\begingroup$ @ArchisWelankar I am answering his question. There is nothing to add. And you downvote, what a ridiculous behaviour. $\endgroup$
    – Thinking
    Dec 14 '18 at 12:33
5
$\begingroup$

You need to show that $(n+1)^{n+1} \geq (n+1)!$, not that $n^{n+1} \geq (n+1)!$.

Here are some similar questions asked before: you can check your work against any of them if you'd like.

For future reference, Approach0 is an excellent resource to search for similar questions (much better than the SE functionality itself). All the best.

$\endgroup$
1
$\begingroup$

As an alternative: $$ n! = \underbrace{{n(n-1)(n-2)\cdots 3\cdot 2\cdot 1}}_{n\ \text{times}} \\ n^n = \underbrace{n \cdot n\cdot n \dots n}_{n\ \text{times}} $$

Note that: $$ {n! \over n^n} = \frac{n(n-1)(n-2)\cdots 3\cdot 2\cdot 1}{n \cdot n\cdot n \dots n} = \\ = \frac{n}{n} \cdot \frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \frac{2}{n} \cdot \frac{1}{n} $$

Now note that for any $n \ge 2$: $$ \frac{n!}{n^n} < 1 $$

$\endgroup$

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