# Alternating sum of square roots of binomial coefficients

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.

• If you denote $\sum_{r=0}^n (-1)^r \binom{n}{r}^\alpha$ by $f(n,\alpha)$, then $f(2n,1)=0, f(2n,0)=1$, and $f(2n,\alpha)$ seems to be decreasing with $\alpha$ for every $n$. That fact (which is stronger than both conjectures you mentioned) may be more feasible. – Mark Sapir Jan 6 '12 at 0:51
• Mark, yes, the positivity of this infinite set of finite sums feels to me quite similar to (and, as you point out, implies) the positivity of the infinite series I asked about earlier in the question you reference, and suffers from the same delicate cancellation of huge quantities. I sort of suspect that if you could crack the infinite series, you could crack this, too. – J Russell Jan 6 '12 at 2:06
• Indeed $c_n>0$, read my response below. In a similar fashion $c_n>c_{n+2}$ should follow, too. – GH from MO Jan 6 '12 at 6:18
• A related (and fairly easy) fact is $\lim_{n\rightarrow\infty}\sum_{k=0}^{2n}(-1)^k{2n\choose k}^{1/{2n\choose k}}=1$. – Roland Bacher Jan 6 '12 at 10:21
• $n\longmapsto \sum_{r=0}^{2n}(-1)^r{2n\choose r}^\alpha$ seems to be bounded for all real $\alpha\leq 3/2$ and seems to be unbounded for $\alpha>3/2$. – Roland Bacher Jan 6 '12 at 18:12

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.

• Beautiful argument. – GH from MO Jan 6 '12 at 7:51
• Personally I find the last sentence a bit confusing. I would say: if a function $g$ has positive derivative, then its first finite difference $g(x)-g(x+1)$ is positive; repeating this argument $n$ times, we find that if the $n$-th derivative is positive then the $n$-th finite difference is also positive. – GH from MO Jan 6 '12 at 8:11
• Just to fill in a gap that bothered me, you need to know that the Taylor series converges in the relevant range. That's true because the first pole of the $\Gamma$ function is at $0$ and it has no zeroes, so $\log \Gamma(r+1)+ \log \Gamma(n-r+1)$ is analytic on a disc centered at $n/2$ of radius $n/2+1$, which encloses the region we care about. Other than that, gorgeous argument! – David E Speyer Jan 6 '12 at 13:24
• @GH & @David Speyer & @Mark Wildon: Thanks! \\ @David: Yes, I'll add the remark about the circle of convergence when I edit this later today to fix or improve some other details. \\ @GH: I don't see that either approach is obviously clearer (once we correct $g(x) - g(x+1)$ to $g(x+1) - g(x)$). My initial $g$ doesn't have $g'\geq 0$ everywhere. Basically it's an intermediate-value result, or a formula for the $n$-th finite difference as a convolution of the $n$-th derivative with the convolution power $\chi_{[0,1]}^{*n}$ where $\chi=$ characteristic function. But that may mystify some too... – Noam D. Elkies Jan 6 '12 at 17:23
• @Noam: I meant that you are really arguing by induction on $n$, and it would be cleaner to say it that way. Here is something more fun: your argument also gives $\sum_{r=0}^n {n\choose r}^\alpha a^r b^{n-r}\geq 0$ for any real $a$ and $b$, even $n$, and $\alpha\leq 1$. Indeed, this can be reduced to $\sum_{r=0}^n (-1)^r{n\choose r}^\alpha f(n,r;x,y)\geq 0$ for $x,y>0$, where $f(n,r;x,y):=(x/y)^{r-\frac{n}{2}}+(y/x)^{r-\frac{n}{2}}=\sum_{m=0}^\infty a_m\left(r-\frac{n}{2}\right)^{2m}$ with $a_m:=(\log x-\log y)^{2m}/(2m)!\geq 0$. The statement follows as in your original post. – GH from MO Jan 6 '12 at 18:19

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.

• Thank you very much for this proof. I would accept your answer as well if I could. I was able to read all but the end of Section 6.6 of de Bruijn's book via Google Books. He considers the sum $c_n$ for general $\alpha \in (0,1)$, saying 'It should be admitted that this is not a very natural question, as non-integral powers of binomial coefficients do not frequently occur in mathematics. The main reason for its discussion here is, that it is a difficult problem with various interesting aspects'. – Mark Wildon Jan 6 '12 at 17:55
• Mark, thank you. I don't know how to make this argument work for any $\alpha \in (0,1)$ since in general the integral is more wildly oscillating. Well, we can restrict to rational $\alpha$ which makes the oscillation more regular. At any rate, you can find and download de Bruijn's book off the internet (link not given, to avoid charges of 'piracy'). – GH from MO Jan 6 '12 at 18:25