7

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}$).

Martin Zhang
  • 183
  • 1
    You should be able to compare the size of the central binomial coefficient with nearby coefficients to see that a small number are close in size to contribute to your sum , and most of the rest do not. I might expect something like a log n term though. Gerhard "It's Not Quite Hump Day" Paseman, 2017.01.03 – Gerhard Paseman Jan 04 '17 at 00:24
  • 2
    I wouldn't even expect a log term. The OP's heuristic (comparison with a square root of the matching Gaussian) should be easy to convert to a proof. – Noam D. Elkies Jan 04 '17 at 01:13
  • 2
    If memory serves, this problem (for any positive exponent) is considered in de Bruijn, Asymptotic Methods in Analysis. I don't have access to this book at the moment. – Richard Stanley Jan 04 '17 at 02:00
  • The last example in Concrete Mathematics is to derive asymtotics for $\binom{n}{k}$ from Stirlings formula and verify $\sum_k \binom{n}{k} = 2^n(1+o(1))$. This somewhat ridiculous finale should be easy to adapt to this problem. – David E Speyer Jan 04 '17 at 02:24
  • Note that rather than using Stirling's formula to prove $\sum_k \binom nk=2^n(1+o(1))$, one can instead use $\sum_k \binom nk=2^n$ to prove Stirling's formula. – Richard Stanley Jan 04 '17 at 02:33
  • @RichardStanley I don't see it in de Bruijn's book, though I could miss it. There are some similar alternating sums. – Brendan McKay Jan 04 '17 at 02:46
  • 1
    I just looked at de Bruijn: the closest example is $\sum(-1)^{n+k}\sqrt{\binom{2n}k}$, and the proof runs through pp.109-119. It's complicated. Of course, it does consider other real powers of the binomial, not just $\frac12$ (always alternating sums). – T. Amdeberhan Jan 04 '17 at 02:59
  • @T.Amdeberhan dB says that the power is an integer. I'm not sure the method works for $s=1/2$. – Brendan McKay Jan 04 '17 at 03:01
  • Please see page 109 and the estimates on page 119. Yes, in the earlier chapters the powers were integers. – T. Amdeberhan Jan 04 '17 at 03:06
  • A quick bound from Cauchy-Schwarz is $\sum_{k=0}^n\sqrt{n\choose k}\le \sqrt{n+1}\sqrt{\sum_{i=0}^n {n\choose i}}=\sqrt{n+1} \ 2^{n/2} $. Moreover, since the mass of the binomial distribution is concentrated at the indices $|n/2 - i|\le \sqrt{n}$, the same inequality for $\sum_{|n/2 - i|\le \sqrt{n}}$ would lower the bound to $Cn^{1/4}2^{n/2}$. – Pietro Majer Jan 04 '17 at 13:35
  • 1
    You might find something about asymptotic of this sum also in this math.SE post: How to evaluate $\sum\limits_{k=0}^{n} \sqrt{\binom{n}{k}} $. There is also a generalization: An asymptotic expression of sum of powers of binomial coefficients.. Found using Approach0. – Martin Sleziak Jan 04 '17 at 14:18
  • 1
    The alternating sum $\sum_k (-1)^{n+k} \sqrt{2n \choose k}$ that T. Amdeberhan refers to is much subtler to estimate. As it happens this sum (and likewise for other fractional powers) appeared here five years ago: http://mathoverflow.net/questions/85013/alternating-sum-of-square-roots-of-binomial-coefficients – Noam D. Elkies Jan 05 '17 at 04:06

2 Answers2

9

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.

Brendan McKay
  • 37,203
  • 3
    No need for Euler-MacL.: the integrand increases to and decreases from $k=0$, so the difference between integral and sum is bounded by the central contribution, which is about $n^{-1/2}$ times the integral. (In fact by Poisson the difference is much smaller, but Stirling incurs an approximation error too.) – Noam D. Elkies Jan 04 '17 at 02:50
4

Define the complex-variable function $$g(z)=\frac{\sin\pi z}{\pi z}\prod_{k=1}^n\frac1{1-\frac{z}k}.$$ Note $f(k)=\binom{n}k$ for $k\in\mathbb{Z}^{\geq0}$. Moreover, $\sqrt{g(z)}$ is analytic in the region $-1<\Re(z)<n+1$ since $g(z)$ is zero-free there. By the Residue Theorem, $$\sum_{k=0}^n\sqrt{\binom{n}k} =\frac1{2\pi i}\int_C\sqrt{g(z)}\,\frac{\pi\cos\pi z}{\sin\pi z}\,dz$$ where $C$ is a closed (positive) contour inside $-1<\Re(z)<n+1$ going around once about each integer $0\leq k\leq n$. Choose $C_R$ as the rectangular along the lines $\Re(z)=-\frac12$, $\Re(z)=n+\frac12$ and $\Im(z)=\pm R$. Thus $$\int_{C_R}\sqrt{g(z)}\,\frac{\pi\cos\pi z}{\sin\pi z}\,dz =\int_{C_R}\prod_{k=1}^n\sqrt{\frac1{1-\frac{z}k}}\,\frac{\sqrt{\pi}\cos\pi z} {\sqrt{z\sin\pi z}}\,dz.$$ So, letting $R\rightarrow\infty$, we arrive at $$\sum_{k=0}^n\sqrt{\binom{n}k} =\frac1{2\pi i}\left[\int_{-\frac12+i\infty}^{-\frac12-i\infty} +\int_{n+\frac12-i\infty}^{n+\frac12+i\infty} \sqrt{g(z)}\,\frac{\pi\cos\pi z}{\sin\pi z}\,dz\right].$$ The integrand is invariant under $z\rightarrow n-z$, hence it suffices to compute (actually estimate) one of the integrals.

This is where I left off. Perhaps someone can complete the argument.

T. Amdeberhan
  • 41,802