0
$\begingroup$

What I've got so far is this:

Base case: n = 3

then $3 *2 * 1 = 6$ and $3^3 = 27$ $\therefore 6 < 27, 3! < 3^3$

So the base case is true.

So if we assume $n! < n^n$ (n > 2)

$(n + 1)! = (n + 1) * n!$

$(n + 1)n! < (n+1)n^n$ # since $n! <n*n$ (can I do this?)

Here is where I am stuck. I know $n^n < (n+1)^n$ where n > 2 I don't know how to prove this step by induction. However if I were to assume this:

$(n+1)n^n < (n+1)(n+1)^n$

$(n+1)n^n < (n+1)^{n+1}$

Then finally, because of all those inequalities,

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

Does this look correct? Can I assume $n^n < (n+1)^n$? If not, how would I prove it, preferably by induction?

$\endgroup$
4
  • $\begingroup$ Do you have to do it via induction? $\endgroup$ Jul 24, 2014 at 6:23
  • $\begingroup$ The proof itself, unfortunately yes, but the sub-proof for $n^n < (n+1)^n$, no. $\endgroup$ Jul 24, 2014 at 6:26
  • 1
    $\begingroup$ Another way is to use Stirling's approximation. $\endgroup$
    – Mathsource
    Jul 24, 2014 at 6:26
  • $\begingroup$ If you really want to, you can show by induction on $n$ that if $a$ is a positive integer then $a^n \lt (a+1)^n$. $\endgroup$ Jul 24, 2014 at 6:30

5 Answers 5

5
$\begingroup$

Use the induction method:

First, take $n=3$, $3! = 6$ and $3^3 =27$, $3! < 3^3$.

Second, assume the inequality holds for $n = K$, $K \in \mathbb{N}$, $K>3$, i.e. $K! < K^K$. Then consider $n= K+1$,

$(K+1)! = (K+1) K! < (K+1) K^K < (K+1) (K+1)^K = (K+1)^{K+1} $,

which is $(K+1)! < (K+1)^{K+1}$.

Proved.

$\endgroup$
3
$\begingroup$

Via induction it's a bit tiresome but

Base case $n=2$, $2!=2<4=2^2$ is pretty straightforward.

Then multiplying both sides by $n+1$ gives

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

Considering

$$(n+1)n^n < (n+1)(n+1)^n=(n+1)^{n+1}$$

so by induction we are done.


Again, a direct proof is infinitely easier, for $n\ge 2$, so I include it for comparison's sake.

$$\log(n!)=\sum_{k=1}^n\log k< \sum_{k=1}^n\log n =n\log n=\log (n^n)$$

$\endgroup$
0
1
$\begingroup$

We know that $n!<n^n$ for some $n$, via our inductive hypothesis. We want to show that $(n+1)!<(n+1)^{n+1}$. Your first step is good, multiplying both sides of our inductive hypothesis by $n+1$ to get $(n+1)!<(n+1)n^n$. But $n^n<(n+1)^n$ (we can assume this, if not, it is very easy to prove), so $(n+1)(n^n)<(n+1)(n+1)^n$ and we have that $(n+1)!<(n+1)^{n+1}$ as desired.

$\endgroup$
0
$\begingroup$

$$(n+1)!$$

$=$ { by definition of the factorial }

$$(n+1)\ n!$$

$<$ { by the recurrence hypothesis }

$$(n+1)\ n^n$$

$<$ { by monotonicity of the $n^{th}$ power }

$$(n+1)(n+1)^n.$$ $=$ { by distributivity of exponentiaition over multiplication } $$(n+1)^{n+1}.$$ And $$3!<3^3.$$

$\endgroup$
0
$\begingroup$

As MathFacts suggested, using Stirling approximation for $n!$ could help. Limited to the very first terms, this approximation write $$n!\simeq n^n \sqrt{2 \pi n}e^{-n}$$ So $n! < n^n$ reduces to $$1 \lt\sqrt{2 \pi n}e^{-n}$$ which is obviously true for any $n \gt 2$.

$\endgroup$

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.