give a detailed proof of the following inequality for all integers n > 1

Question

a) give a detailed proof of the following inequality for all integers n > 1 $$ \frac{{2}^{n}}{n} \leq {n \choose \lfloor{\frac{n}{2}}\rfloor}$$

This is what I have so far: $$\frac{{2}^{n}}{n} \leq {n \choose \lfloor{\frac{n}{2}}\rfloor}$$ $$ {n} \frac{{2}^{n}}{n} \leq {n}{n \choose \lfloor{\frac{n}{2}}\rfloor}$$ $$ \sum_{0 \leq k \leq n} {n \choose k} \leq {n}{n \choose \lfloor{\frac{n}{2}}\rfloor} $$

How do I finish this?

b) give a detailed proof of the following inequality for all integer n $\geq$ 1 $$ \sqrt{{n}^{n}} \leq n! $$

This is what I have so far: $$ \sqrt{{n}^{n}} \leq n! $$ $$ {n}^{\frac{n}{2}} \leq {n}\times{(n - 1)}\times{...}\times{2}\times{1} $$ $$ {n}^{\frac{n}{2}}\times{...}\times{n}^{\frac{n}{2}} \leq {n}\times{(n - 1)}\times{...}\times{2}\times{1} $$ length of $\frac{n}{2} \leq$ length of n

I have shown that the length is less, but how do I show it is less overall?

Answer 1

a) Because the "middle" binomials are the largest one $$1=\binom{n}{0}<\binom{n}{1}<\dots<\binom{n}{\left \lfloor n/2 \right \rfloor}=\binom{n}{\left \lceil n/2 \right \rceil}>\dots>\binom{n}{n-1}>\binom{n}{n}=1$$ so we have what you want.

Answer 2

For a), you just need the fact ${n\choose k}\leq{n\choose\lfloor n/2\rfloor}$ for all $0\leq k\leq n$. To see this, suppose $n$ is even and $k<n/2$, then

\begin{align} {n\choose n/2}&={n\choose k}\times\frac{n-k}{k+1}\times\frac{n-k-1}{k+2}\times\cdots\times\frac{n/2+1}{n/2}\\[.8em] &\geq{n\choose k}\times\frac{n/2+1}{n/2}\times\frac{n/2+1}{n/2}\times\cdots\times\frac{n/2+1}{n/2}\geq{n\choose k}. \end{align} The situation for $k>n/2$ is exactly reversed, and you can easily use the same arguments for odd $n$.

---

For b), you can easily show $(n-m)(m+1)\geq n$ for all integer $0\leq m<n$. Then again assume $n$ is even, we have

$$n^{n/2}=\prod_{m=0}^{n/2-1}n\leq\prod_{m=0}^{n/2-1}(n-m)(m+1)=n!.$$

For odd $n$, use the same idea with the bound $\sqrt n\leq(n+1)/2$.