0

Prove by induction $n^{n}>2^{n}\times n!$ for all $n\geq6$.

This is what I've got at the moment. Still not sure whether is the right way to solve it by induction:

Basic Step: Show that $S(1)$ is true for $n=6$: $$6^{6}>2^{6}\text{·}6!$$ $$46656>46080$$

...

Induction step: Show that $S\left(n+1\right)$ is true, that is: $$(n+1)^{(n+1)}>2^{n+1}\times(n+1)!$$ Adding $(n+1)$ to both sides of $n^{n}>2^{n}\times n!$ we have $$\left(n+1\right)n^{n}>2^{n}\times\left(n+1\right)n!$$

$$n^{n+1}+n^{n}>2^{n}\times\left(n+1\right)!$$

Diego Gallo
  • 161
  • 2
    If $n=3$ so you don't have that $3^{3}>2^{3}3!$. So, the statement is not true. –  Nov 04 '20 at 05:08
  • 1
    I believe you have written the inequality wrong. It is false as Albus Dumbledore has stated. – Derek Luna Nov 04 '20 at 05:32

1 Answers1

1

The inequality you would like to prove is rather

$$n^n < \color{blue}{3}^n\cdot n!$$

A proof by induction can be done using the fact that

$$\left(1+\frac 1n\right)^n < 3 \text{ for all } n \in \mathbb{N}$$

The induction step could then look as follows:

Under the assumption that $n^n < 3^n\cdot n!$ is true, to show is $$(n+1)^{n+1} < 3^{n+1}\cdot (n+1)!$$ or equivalently $$(n+1)^n < 3\cdot 3^n\cdot n!$$

But this is true because

$$(n+1)^n = \frac{(n+1)^n}{n^n}\cdot n^n$$ $$ = \left(1+\frac 1n\right)^n\cdot n^n < 3\cdot n^n \stackrel{n^n < 3^n\cdot n!}{<} 3\cdot 3^n\cdot n!$$

trancelocation
  • 32,243
  • So, a takeaway for this would be that as for inequalities, induction method proof won't always depend on the mechanical process of applying arithmetics tricks such that I pass from case (n) to exatly the same expression as case (n+1) as happens with induction and summation? – Diego Gallo Nov 04 '20 at 15:53
  • @DiegoGallo Correct. An induction step can turn out to be quite tricky and may not just rely on some arithmetic tricks. Note that my response to your question comes quite late because we seem to live in quite different time zones. – trancelocation Nov 05 '20 at 05:32