Question: let
\begin{equation}
c_n=\sum_{i=0}^n \sqrt{\binom{n}{i}}.
\end{equation}
How does $c_n$ grow with $n$?
My conjecture is that $c_n=\Theta(2^{0.5n}n^{0.25})$.This is because
\begin{equation}
0.5^{0.5n} c_n = \sum_{i=0}^n \sqrt{\binom{n}{i}0.5^n}=\sum_{i=0}^n\sqrt{Pr(X=i)},
\end{equation}
for $X\sim Bin(n,0.5)$. The binomial distribution $Bin(n,0.5)$ is approximately the normal distribution $N(0.5n, 0.25n)$. Also, if $Y\sim N(0.5n, 0.25n)$, it is not hard to see that
\begin{equation}
\int \sqrt{f(y)} dy =\Theta(n^{0.25}).
\end{equation}
Therefore I believe that it is also true that $0.5^{0.5n} c_n=\Theta(n^{0.25})$. I played with matlab to get some evidence and found that
\begin{equation}
\frac{0.5^{0.5n} c_n}{n^{0.25}} \approx \frac{\pi}{2},
\end{equation}
for $n=100,1000,10000,100000,1000000$. So the conjecture should be true. So anyone can prove it?
(It turns out that $\frac{0.5^{0.5n} c_n}{n^{0.25}} \approx (2\pi)^{0.25}$ instead of $\frac{\pi}{2}$).
Best Answer
For smallish $k$, we have $$ \binom{n}{n/2+k} \approx \binom{n}{n/2} \exp(-2k^2/n). $$ So $$\sum\sqrt{\binom{n}{n/2+k}} \approx \sqrt{\binom{n}{n/2}} \int_{-\infty}^\infty e^{-k^2/n}\,dk \approx 2^{n/2} (2\pi n)^{1/4}.$$ Of course I did some hand-waving here, but all of this is rigorously justifiable. Use the Euler-Maclaurin theorm to justify replacing the sum by an integral.