7
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Jan 4 '17 at 0:24
  • 2
    $\begingroup$ 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. $\endgroup$ – Noam D. Elkies Jan 4 '17 at 1:13
  • 2
    $\begingroup$ 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. $\endgroup$ – Richard Stanley Jan 4 '17 at 2:00
  • 1
    $\begingroup$ 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). $\endgroup$ – T. Amdeberhan Jan 4 '17 at 2:59
  • 1
    $\begingroup$ 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. $\endgroup$ – Martin Sleziak Jan 4 '17 at 14:18
8
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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.) $\endgroup$ – Noam D. Elkies Jan 4 '17 at 2:50
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I like $\sqrt{g}$, it reminds me the frequency of the pendulum $\endgroup$ – Pietro Majer Jan 4 '17 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.