3
$\begingroup$

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?

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

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.

$\endgroup$
2
$\begingroup$

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) $$

$\endgroup$
  • $\begingroup$ Essentially the same as Daniel Robert-Nicoud above -- in hindsight, my post doesn't bring much to the table. $\endgroup$ – Clement C. Jan 22 '14 at 20:55
1
$\begingroup$

$$2(n+1)^{n+1}\leq\sum_{k=0}^{n+1} \binom {n+1}k(n+1)^{n-k+1}= (n+2)^{n+1} .$$

$\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.