Show by induction that $n^n>2^{n+1}$

Question

I have been asked to prove $n^n>2^{n+1}$ for every natural number $\ge$ 3

I have understood the Induction Basis and Hypothesis :

Induction Basis : n=3 ; 27>16

Induction Hypothesis : let n $\ge$ 3 such that $n^n>2^{n+1}$

However, I struggle to understand the following statement

Induction Step: $(n + 1)^{n+1} > n^n· n >(IH) 2^{n+1}· n > 2 ^{n+2}$

My issue with the IS is how one arrives at $2^{n+1}· n$ from $2 ^{n+2}$.

I can see that with the LHS of the IS has been expanded and any constants have been removed because they are of 'lower impact' than the other $n^n$ expression but can't see how the issue above works.

Answer 1

I can see that with the LHS of the IS has been expanded and any constants have been removed because they are of 'lower impact' than the other $n^n$ expression but can't see how the issue above works.

I don't see what has been expanded and where any constants have been removed.

The statement that we need to prove is:

Induction step. If $n\ge 3$ and $n^n > 2^{n+1}$, then $(n+1)^{n+1} > 2^{n+2}$.

To do this: first, for any integers $x>0$ and $n>0$, it is elementary that $(x+1)^{n+1} > x^{n+1}$. Hence, for $x = n$,

$$(n+1)^{n+1} > n^{n+1} = \color{blue}{n^n} \cdot \color{red}n.$$

Now, the induction hypothesis is that $\color{blue}{n^n > 2^{n+1}}$. So we plug this in to get $$ \color{blue}{n^n} \cdot {\color{blue}{\color{red}n > 2^{n+1}}} \cdot \color{red}n.$$ And we haven't yet used the assumption $\color{red}{n\ge 3}$; we should do so now (as the comment of Eureka points out) $$ \color{blue}{2^{n+1}} \cdot \color{red}{n \ge \color{blue}{2^{n+1}} \cdot 3} > 2^{n+1} \cdot 2 = 2^{n+2}.$$ This completes the induction step, by joining the three inequalities together.

Answer 2

Since $n\geqslant3$, then $n>2$, and therefore $2^n\times n>2^n\times2=2^{n+1}$.

Answer 3

If your formula is exact, the induction hypothesis is $\;n^n>2^{n\color{red}{+1}}\enspace (n\ge 3)$. So \begin{align} (n+1)^{n+1}=(n+1)^n(n+1)>n^n\cdot n &>2^{n+1}\cdot 2=2^{n+2}.\cr &\downarrow \\ \text{(inductive}&\text{ hypothesis)} \end{align}