Alternating sum of square roots of binomial coefficients - MathOverflow

Alternating sum of square roots of binomial coefficients

2012-01-06T00:20:12Z

Let $$ c_n = \sum_{r=0}^n (-1)^r \sqrt{\binom{n}{r}}. $$ It is clear that $c_n = 0$ if $n$ is odd. Remarkably, it appears that despite the huge positive and negative contributions in the sum defining $c_{2m}$, the sequence $(c_{2m})$ may be very well behaved.

Is $c_n > 0$ for all even $n$?

An affirmative answer will imply that the function $F(x) = \sum_{n=0}^\infty x^n/\sqrt{n!}$ is always strictly positive, thereby answering this earlier question.

Numerical computation using Magma shows that $c_n > 0$ if $n$ is even and $n \le 2000$. To give some illustrative values, $c_{100} = 0.077737 \ldots$, $c_{1000} = 0.019880 \ldots $ and $c_{2000} = 0.013317 \ldots$.

A comment by Mark Sapir on the earlier question suggests a stronger result might hold.

Is $c_{n} > c_{n+2} > 0$ for all even $n$?

I have checked that this is the case for all even $n \le 2000$.

It is very natural to ask what happens if we replace $\sqrt{\binom{n}{r}}$ with $\binom{n}{r}^\alpha$ for $\alpha \in (0,1)$. For $n\le 250$ the generalized version of the conjecture continues to hold if $\alpha = k/10$ where $k \in \mathbf{N}$ and $k \le 9$. Of course when $\alpha = 1$ we have $c_n = 0$ for all $n$, so, as David Speyer remarked in a comment on the earlier question, there is a good reason for the cancellation in this case.

Answer by GH for Alternating sum of square roots of binomial coefficients

2012-01-06T05:55:21Z

The following proof of $c_n>0$ is based on Gjergji Zaimi's response to this related question. In particular the positive answer follows for that question, too. Moreover, the argument below should also show that $c_n>c_{n+2}$.

Let $n>0$ be even. By Chapter 6 of de Bruijn's "Asymptotic Methods in Analysis" (in particular by (6.4.6), (6.6.2), and the conclusion $P=0$ of Section 6.5), we have the following explicit formula:

$$ c_n = 2\pi^{-1/2}\sqrt{n!}\ \sum_{m=0}^\infty \ \int_{4m+1}^{4m+2} G_n(x)\ |\sin\pi x|^{-1/2}dx, $$

where

$$ G_n(x) := \sqrt{\frac{\Gamma(x)}{\Gamma(1+x+n)}}- \sqrt{\frac{\Gamma(2+x)}{\Gamma(3+x+n)}}.$$

It remains to verify that $G_n(x)>0$ for $x\geq 1$. This reduces to

$$\Gamma(x)\Gamma(3+x+n)>\Gamma(2+x)\Gamma(1+x+n),$$

i.e. to

$$ (1+x+n)(2+x+n)>x(1+x). $$

The last inequality is obvious, hence we are done.

Answer by Noam D. Elkies for Alternating sum of square roots of binomial coefficients

2012-01-06T06:53:41Z

Here's a proof of the positivity of $$ c_n(\alpha) := \sum_{r=0}^n (-1)^r {n\choose r}^\alpha $$ for all even $n$ and real $\alpha < 1$. It follows (via M.Wildon's clever $F(x) F(-x)$ trick at mo.84958) that $\sum_{n=0}^\infty \phantom. x^n / n!^{\alpha} > 0$ for all $x \in\bf R$. [EDIT fedja has meanwhile provided a very nice direct proof of the positivity of $\sum_{n=0}^\infty \phantom. x^n / n!^{\alpha}$.]

The key is to write $c_n(\alpha)$ as a finite difference $$ \sum_{r=0}^n \phantom. (-1)^r {n\choose r} \cdot {n\choose r}^{\alpha - 1} $$ and show that the Gamma interpolation $$ \bigl(\Gamma(r+1)\Gamma(n-r+1) / n!\bigr)^{1-\alpha} = n!^{\alpha-1} \exp\bigl((1-\alpha) (\log\Gamma(r+1) + \Gamma(n-r+1)\bigr) $$ of ${n\choose r}^{\alpha - 1}$ has a positive $n$-th derivative for all $r \in [0,n]$.

This in turn follows from the fact that the expansion of $\log\Gamma(r+1) + \log\Gamma(n-r+1)$ in a Taylor series about $r = n/2$ has positive $(r - (n/2))^k$ coefficient for each $k=2,4,6,\ldots$. [The coefficient vanishes for odd $k$ because $\log\Gamma(r+1) + \log\Gamma(n-r+1)$ is an even function of $r-(n/2)$.] Indeed the well-known formula $$ \log \Gamma(x) = -\gamma x - \log x + \sum_{j=1}^\infty \left[ \frac{x}{j} - \log \left( 1 + \frac{x}{j} \right) \right] $$ shows that the $k$-th derivative of $\log\Gamma(x)$ is positive for all $x>0$ and $k=2,4,6,\ldots$, because this is true for $-\gamma x - \log x$ and for each term in the sum; explicitly the derivative is $k! \phantom. \sum_{j=0}^\infty (x+j)^{-k}$ which is positive termwise. Therefore in the Taylor expansion $$ \log \Gamma(r+1) = \log(n/2)! + \sum_{k=1}^\infty \phantom. g_k (r-(n/2))^k $$ each of $g_2,g_4,g_6,\ldots$ is even. Since $\log\Gamma(r+1) + \log\Gamma(n-r+1)$ is $$ 2\log(n/2)! + 2 \Bigl( g_2 (r-(n/2))^2 + g_4 (r-(n/2))^4 + g_6 (r-(n/2))^6 + \cdots\Bigr), $$ the claim follows. [EDIT David Speyer notes that the convergence of the Taylor series on $|r-(n/2)| \leq n/2$ requires justification, and that the justification is easy because the $\Gamma(z)$ has no zeros and poles only at $0,-1,-2,\ldots$ so the radius of convergence is $(n/2)+1$.] Multiplying by $1 - \alpha$ and substituting into the exponential series, we deduce that $(\Gamma(r+1) \Gamma(n-r+1))^{1-\alpha}$, too, is a positive combination of even powers of $r-(n/2)$.

Now if a function $g$ has positive $n$-th derivative, then its first finite difference $$ g(x+1) - g(x) = \int_x^{x+1} g'(y) dy $$ has positive $(n-1)$-st derivative; repeating this argument $n$ times, we find that the $n$-th finite difference is positive, and we're done.