How to evaluate $\sum\limits_{k=0}^{n} \sqrt{\binom{n}{k}} $ Can we find $$ \sum_{k=0}^{n} \sqrt{\binom{n}{k}} \quad$$
This problem asked me my friend about a year ago, but I didn't know how to attack problem. Now, I am interesting in solution. Any suggestion?
 A: $$\left(\sum_{k=0}^{n} \sqrt{\binom{n}{k}} \right)^2 \geq \sum_{k=0}^{n} \binom{n}{k}=2^n$$
Thus
$$\sum_{k=0}^{n} \sqrt{\binom{n}{k}} \geq 2^{\frac{n}{2}}$$
Also, by C-S
$$\left(\sum_{k=0}^{n} \sqrt{\binom{n}{k}} \right)^2 \leq (n+1)2^n$$
thus
$$\sum_{k=0}^{n} \sqrt{\binom{n}{k}}\leq 2^{\frac{n}{2}} \sqrt{n+1}$$
A: For any positive power $p$, $\displaystyle \sum\limits_{k=1}^{n} \binom{n}{k}^p \sim \dfrac{2^{np}}{\sqrt{p}}\cdot\left(\frac{n\pi}{2}\right)^{(1-p)/2} $,
Making, $n \mapsto 2n$,
We have, $\displaystyle \dfrac{\binom{2n}{n-k}}{\binom{2n}{n}} = \dfrac{n}{n+k}\prod\limits_{j=1}^{k-1}\dfrac{1-\frac{j}{n}}{1+\frac{j}{n}} = \dfrac{n}{n+k}e^{\sum\limits_{j=1}^{k-1}\log\frac{1-j/n}{1+j/n}}$
and form taylor expansion at $t=0$, $\log \dfrac{1-t}{1+t} = -2t - \dfrac{2x^3}{3}+O(t^5)$,
so, $0 < -2t - \log\dfrac{1-t}{1+t} = O(t^3) $ for, $0 < t < 1/2$.
It sufices to look at the central $n^{2/3}$-terms, 
since, $\displaystyle \dfrac{\binom{2n}{n-k}}{\binom{2n}{n}} = \dfrac{n}{n+k}\large{e^{\sum\limits_{j=1}^{k-1}\log\frac{1-j/n}{1+j/n}}}$ $ = \begin{cases}(1+O(n^{-1/3}))e^{-k^2/n} & \textrm{ for } k\le n^{2/3} \\ O(e^{-n^{1/3}})  & \textrm{ for } k>n^{2/3}\end{cases}$
Hence, $\displaystyle \sum_{k=1}^{n-1} \dfrac{\binom{2n}{n-k}^p}{\binom{2n}{n}^p} = (1+O(n^{-1/3}))\sum\limits_{k=1}^{n^{2/3}} e^{-pk^2/n} + o(1) = (1+O(n^{-1/3}))\int_1^{n^{2/3}} e^{-pt^2/n}\,dt + O(1)$
$$\sim \frac{1}{2}\sqrt{\dfrac{n\pi}{p}}$$
Using Stirling Approximation we have, $\displaystyle \binom{2n}{n} \sim \dfrac{4^{n}}{\sqrt{n\pi}}$
Hence, $\displaystyle \sum\limits_{k=1}^{n} \binom{n}{k}^p \sim \dfrac{2^{np}}{\sqrt{p}}\cdot\left(\frac{n\pi}{2}\right)^{(1-p)/2} $
A: Here is an asymptotic approximation rather than an evaluation.
If we take the first difference of the log of $\sqrt{\binom{n}{k}}$, we get
$$
\frac12\log\left(\frac{n-k+1}{k}\right)\tag{1}
$$
which vanishes when $k\sim n/2$.
If we take the second difference of the log of $\sqrt{\binom{n}{k}}$, we get
$$
\frac12\log\left(\frac{k-1}{k}\right)-\frac12\log\left(\frac{n-k+2}{n-k+1}\right)\sim-\frac1{2k}-\frac1{2(n-k+1)}\tag{2}
$$
This is approximately
$$
-\frac2n\tag{3}
$$
where the first difference vanishes.
Approximating the sum by a Gaussian, gives the value of the sum to be asymptotic to
$$
\begin{align}
\overbrace{\sqrt{\textstyle\binom{n}{n/2}}}^{\begin{array}{c}\text{account}\\\text{for the}\\\text{maximum}\end{array}}\cdot\overbrace{\int_{-\infty}^\infty e^{-x^2/n}\,\mathrm{d}x}^{\begin{array}{c}\text{account}\\\text{for second}\\\text{difference}\end{array}}
&\sim2^{n/2}\left(\frac2{\pi n}\right)^{1/4}\cdot\sqrt{\pi n}\\
&=2^{n/2}(2\pi n)^{1/4}\tag{4}
\end{align}
$$
For $n=100$, the sum is $5.62976892\times10^{15}$ and $(4)$ gives $5.63695737\times10^{15}$.
For $n=1000$, the sum is $2.91399232\times10^{151}$ and $(4)$ gives $2.91435733\times10^{151}$.
As $n$ gets larger, the approximation gets better.
