Prove that $(n+1)^n < n^{n+1}$ for all $n>3$ 
Prove that $(n+1)^n < n^{n+1}$ for all $n>3$

At $n=4$, $$5^4<4^5$$  which is indeed true.
By mathematical induction, we need to prove that $$(n+2)^{n+1} < (n+1)^{n+2}$$
$$\implies (n+2)^n\times (n+2) < (n+1)^n\times(n+1)^2 $$
I am not getting how to proceed further than this. Any hints or help would be highly appreciated! Thanks.
 A: Here's a proof by induction:
Base case: Done by OP.
Induction step:
Notice that $(n+1)^{2(n+1) } = (n^2 + 2n + 1) ^ {n+1} > [ (n)(n+2) ] ^ {n+1}$.

 Since $ (n+1) ^ n < n^ {n+1} $ by the induction hypothesis,
 so $ [ (n)(n+2) ] ^ {n+1} < (n+1)^{2(n+1) } < (n+1) ^ {n+2} n ^ {n+1} $,

hence it follows that $(n+2)^{n+1} < (n+1)^{n+2}$.

Notes

*

*The "notice that" step might initially seem like magic. However, you can backtrack it to see why that's something we would have cared about.

*If that didn't work, we could have tried to prove (say) $(n+1)^{kn+2k-2 } > [n (n+2) ^{k-1}] ^{n+1}$, which would eventually be true for large enough $k$.

*I was previously skeptical that an induction solution existed, because the standard/naive routes didn't seem to result in a $(n+2)$ term, nor was it clear how a $(n+2)^{n+1}$ could be related to a $(n+1)^{n}$. I'm glad to have figured this out.

A: The claim is equivalent to  $\left(1+\frac 1n\right)^n < n$. The sequence on the LHS, whose limit is $e$, is known to remain in the set $[2,3]$. If you can use this fact, the result you want to prove must hold for $n \ge 3$.
A: Using binomial expansion, we can write
\begin{align*}
\text{LHS} &= (n+1)^n\\
&= (n+1)^{n-1}\times (n+1)\\
&= \left[n^{n-1} + {n-1 \choose 1}n^{n-2} + {n-1 \choose 2}n^{n-3} + \cdots + {n-1 \choose n-2}n + {n-1 \choose n-1}\right] \times (n+1)\\
&= \left[n^{n-1} + {n-1 \choose 1}n^{n-2} + {n-1 \choose 2}n^{n-3} + \cdots + {n-1 \choose n-2}n\right] \times (n+1) + (n+1)\\
\end{align*}
For $n > 3$, it is straightforward to show that
$${n-1 \choose k} < n^k$$
for all $k = 1,2,\dots, n-2$. Thus, we have
\begin{align*}
\text{LHS} &< \left[n^{n-1} + n^1n^{n-2} + n^2n^{n-3} + \cdots + n^{n-2}n\right] \times (n+1) + (n+1)\\
&= \left[(n-1)n^{n-1}\right] \times (n+1) + (n+1)\\
&= (n^2 - 1)n^{n-1} + (n+1)\\
&= n^{n+1} - n^{n-1} + (n+1)\\
&< n^{n+1} = \text{RHS},
\end{align*}
where the last step follows from the fact that
$$n^{n-1} > n+1$$
for all $n > 3$.
Remark: In contrast to other answers, this gives a proof without using induction.
A: As noted by Exodd, consider the equivalent problem $(1 + 1/n)^n < n$ (also offered by PierreCarre). If one does not have the relationship with $\mathrm e < 3$ available, prove the equivalent problem by induction instead:
$$\left(1 + \frac{1}{n+1} \right)^n \left( 1 + \frac{1}{n+1} \right) < n\left(1 + \frac{1}{n+1}\right)<n+1.$$
The base case is $625/256 < 4$.
A: $\frac{(n+2)^{n+1}}{(n+1)^{n}} < \frac{(n+1)^{n+2}}{n^{n+1}}$
$\frac{((n+2)n)^{n+1}}{(n+1)^{n}} < \frac{(n+1)^{n+2}}{n^{n+1}}$
$((n+2)n)^{n+1} < (n+1)^{2(n+1)}$
$(n+2)n < (n+1)^{2}$
And it demonstrates the induction step!
A: Here is a non-inductive proof that involves a nice application of the AM-GM inequality.
It suffices for us to prove the following inequality:
\begin{align}
\forall \ & n>3,  \left(1+\dfrac{1}{n}\right)^n <4 \\
& \iff \left(\dfrac{n+1}{n}\right)^n <4 \\
& \iff \left(\dfrac{n}{n+1}\right)^n >\dfrac{1}{4} \\
& \iff \dfrac{n}{n+1} > \sqrt[^n]{\dfrac{1}{4}}
\end{align}
But
\begin{align}
\sqrt[^n]{\dfrac{1}{4}} &= \sqrt[^n]{\dfrac{1}{2} \cdot \dfrac{1}{2} \cdot 1^{n-2}} \\
& \leq \dfrac{\dfrac{1}{2}+ \dfrac{1}{2}+n-2}{n} (\text{By the AM-GM Inequality}) \\
& = \dfrac{n-1}{n}.
\end{align}
It remains to show that $\dfrac{n-1}{n} < \dfrac{n}{n+1}$, which is obvious since $n^2-1 < n^2$.
