Prove that $6^{\sqrt n} = O({n \choose n/2})$

Question

Prove that $6^{\sqrt n} = O({n \choose n/2})$

I was able to show that prove that $6^{\sqrt n} = O({n \choose n/2})$ with defining $ n=2k$ and $ a_k= \frac {k!^26^\sqrt k} {2k!} $ and then show that $\frac {a_{k+1}} {a_k}\rightarrow\frac1 4 \Rightarrow a_k\rightarrow0$ .

I want to see other ways of proving that. Thanks

Answer 1

Presumably $n$ is supposed to be even. Then ${n \choose {n/2}} 2^{-n}$ is the probability $p(n/2)$ of getting exactly $n/2$ heads when tossing $n$ fair coins. Since the distribution of the number of heads is unimodal with mode $n/2$, $p(n/2) > p(k)$ for all other $k$. In particular, since there are just $n+1$ possibilities for the number of heads, $p(n/2) > 1/(n+1)$, i.e. ${n \choose {n/2}} > 2^n/(n+1)$. Can you go on from there?

Answer 2

$$\frac{(n!)^26^{\sqrt{n}}}{(2n)!} = \frac{1\cdot2\cdots(n-1)\cdot n \cdot 6^{\sqrt{n}}}{(n+1)\cdot (n+2) \cdots (2n-1)\cdot 2n} \leq (\tfrac{1}{2})^n6^{\sqrt{n}} \leq (\tfrac{1}{2})^{4\sqrt{n}}6^{\sqrt{n}} \leq (\tfrac{6}{16})^{\sqrt{n}}\rightarrow 0.$$ The first inequality follows since $\frac{1}{n+1},\frac{2}{n+2},\ldots,\frac{n}{2n} \leq \frac{1}{2}$, and the second inequality follows since $n\geq4\sqrt{n}$ (which holds for every $n\geq 16$).