Prove $2^n\cdot n! ≤ (n+1)^n$ by induction.

An induction I'm struggling with.

Prove $2^n\cdot n! ≤ (n+1)^n$ by induction.

An idea was to show that $2^n\cdot n! ≤ 1+n^2$ since $1+n^2 ≤ (n+1)^n$ using Bernoulli. However the inequality is just wrong so that approach doesn't work. I had the intuition that $2^n ≤ n!$ but I don't think that yields anything for this problem.

I would really like to get a hint or two. Of course you can post your answer, this is obviously what this platform is for, but I won't read them until I solved the problem myself. It's an induction, can't be that difficult right?

• $2^n$ is already larger that $n^2+1$ if $n\ge5$, so your idea cannot work. – Andrés E. Caicedo Jan 22 '14 at 20:43
• i wrote that it was just an idea which I quickly abandoned. – Nhat Jan 22 '14 at 20:55

Hint: The induction step goes as follows: $$2^{n+1}(n+1)!=2^nn!2(n+1)\le(n+1)^n2(n+1)=2(n+1)^{n+1}$$ Thus you are left to prove that $2(n+1)^{n+1}\le(n+2)^{n+1}$, which is pretty easy.
Base case, $n = 1$: $2 \leq 2$, true.
Assumenow it holds up to $n\geq 1$. Then, $$2^{n+1}\cdot(n+1)! = 2(n+1)\cdot 2^n\cdot n! \operatorname*{\leq}_{\rm(IH)} 2(n+1)\cdot(n+1)^n = 2(n+1)^{n+1}$$ so to conclude the induction, it boils down to proving that $$2\leq \left(\frac{n+2}{n+1}\right)^{n+1} = \left(1+\frac{1}{n+1}\right)^{n+1} (\operatorname*{\sim}_{n\to\infty} e)$$
$$2(n+1)^{n+1}\leq\sum_{k=0}^{n+1} \binom {n+1}k(n+1)^{n-k+1}= (n+2)^{n+1} .$$