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$
12
  • 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$ Jan 4, 2017 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$ Jan 4, 2017 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$ Jan 4, 2017 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$ Jan 4, 2017 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$ Jan 4, 2017 at 14:18

2 Answers 2

9
$\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$
1
  • 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$ Jan 4, 2017 at 2:50
4
$\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$
1
  • 1
    $\begingroup$ I like $\sqrt{g}$, it reminds me the frequency of the pendulum $\endgroup$ Jan 4, 2017 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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