I am attempting to solve this by induction, yet I am stuck on the last part. Below is my attempted solution.
Show that $\frac{\left(2n\right)!}{2^{n}n!} \ge \frac{\left(2n\right)!}{\left(n+1\right)^{n}}, \forall n \in \mathbf{N} $.
My attempted solution, by induction:
For $n=1$ we have,
$\frac{\left(2\right)!}{2^{1} \cdot 1!} \ge \frac{\left(2\right)!}{\left(1+1\right)^{1}} $
$2 \ge 1$.
Thus, the inequality holds for $n=1$.
Now assume that it holds $\forall k \in \mathbf{N}$.
Then, for $k+1$,
$\left(k+1\right) \frac{\left(2k\right)!}{2^{k}k!} \ge \frac{\left(2k\right)!}{\left(k+1\right)^{k}} \left(k+1\right) $.
This is where I am stuck.
Best Answer
You want to prove $2^n n!\le (n+1)^n$. Use Strling formula or induction on $n$. Here is a proof using induction. When you pass from $n$ to $n+1$ the LHS gets multiplied by $ 2(n+1)$. If you multiply the RHS by this you get $2(n+1)^{n+1}$. This is smaller than $(n+2)^{n+1}$ for all $n>c$ for some relatively small $c$ (I think $c=1$ works already). Indeed dividing both sides by $(n+1)^{n+1}$ you get $(1+1/(n+1))^{n+1}\approx e>2$. Moreover it is bigger than $2$ for $n=1$ already and increases as $n$ gets bigger.