Alternating sum of square roots of binomial coefficients - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T01:04:34Z http://mathoverflow.net/feeds/question/85013 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/85013/alternating-sum-of-square-roots-of-binomial-coefficients Alternating sum of square roots of binomial coefficients Mark Wildon 2012-01-06T00:20:12Z 2012-03-11T18:59:38Z <p>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. </p> <blockquote> <p>Is $c_n > 0$ for all even $n$?</p> </blockquote> <p>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 <a href="http://mathoverflow.net/questions/84958/is-sum-limits-n0-infty-xn-sqrtn-positive" rel="nofollow">earlier question</a>.</p> <p>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$. </p> <p>A comment by Mark Sapir on the earlier question suggests a stronger result might hold. </p> <blockquote> <p>Is $c_{n} > c_{n+2} > 0$ for all even $n$?</p> </blockquote> <p>I have checked that this is the case for all even $n \le 2000$.</p> <p>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.</p> http://mathoverflow.net/questions/85013/alternating-sum-of-square-roots-of-binomial-coefficients/85032#85032 Answer by GH for Alternating sum of square roots of binomial coefficients GH 2012-01-06T05:55:21Z 2012-01-06T06:46:20Z <p>The following proof of $c_n>0$ is based on Gjergji Zaimi's response to this <a href="http://mathoverflow.net/questions/84958/is-sum-limits-n0-infty-xn-sqrtn-positive" rel="nofollow">related question</a>. In particular the positive answer follows for that question, too. Moreover, the argument below should also show that $c_n>c_{n+2}$.</p> <p>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:</p> <p>$$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,$$</p> <p>where</p> <p>$$G_n(x) := \sqrt{\frac{\Gamma(x)}{\Gamma(1+x+n)}}- \sqrt{\frac{\Gamma(2+x)}{\Gamma(3+x+n)}}.$$</p> <p>It remains to verify that $G_n(x)>0$ for $x\geq 1$. This reduces to</p> <p>$$\Gamma(x)\Gamma(3+x+n)>\Gamma(2+x)\Gamma(1+x+n),$$</p> <p>i.e. to </p> <p>$$(1+x+n)(2+x+n)>x(1+x).$$ </p> <p>The last inequality is obvious, hence we are done.</p> http://mathoverflow.net/questions/85013/alternating-sum-of-square-roots-of-binomial-coefficients/85035#85035 Answer by Noam D. Elkies for Alternating sum of square roots of binomial coefficients Noam D. Elkies 2012-01-06T06:53:41Z 2012-01-07T05:33:59Z <p>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 &lt; 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$. [<strong>EDIT</strong> fedja has meanwhile provided a very nice direct proof of the positivity of $\sum_{n=0}^\infty \phantom. x^n / n!^{\alpha}$.]</p> <p>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]$.</p> <p>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. [<strong>EDIT</strong> 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)$.</p> <p>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.</p>