# 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.
– user6976
Jan 6, 2012 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. Jan 6, 2012 at 2:06
• Indeed $c_n>0$, read my response below. In a similar fashion $c_n>c_{n+2}$ should follow, too. Jan 6, 2012 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$. Jan 6, 2012 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$. Jan 6, 2012 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. Jan 6, 2012 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. Jan 6, 2012 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! Jan 6, 2012 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... Jan 6, 2012 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. Jan 6, 2012 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'. Jan 6, 2012 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'). Jan 6, 2012 at 18:25