# Sum with binomial coefficients and a square root

I encountered this sum from working on an integral:

$$\sum_{k=0}^{n}\binom{n}{k}(-1)^{k}\sqrt{k}$$

I don't think it can be written as a hypergeometric function, because of this square root.

Does this sum have a closed form?

• I see no hope that this sum has an expression that is better than the sum itself, since the summands are contain linearly independent roots. However, it is possible that a nice limit for n to infinity exists. – Phira Apr 21 '13 at 21:15
• @Phira That's a good question. The sum seems to behave pretty weirdly from my numerical calculations. – Alexander Gruber May 18 '14 at 1:29
• I think Phira's comment can be adapted into a field-theoretic proof that this isn't a rational function in $n$ (no matter what field the coefficients are in). – Jack M Jun 2 '14 at 21:14

## 2 Answers

A closed form for $$S(n) := \sum_{k=0}^n \binom{n}{k} (-1)^{k} \sqrt{k}$$ is indeed unlikely; at any rate it surely can't be a finite hypergeometric sum, because the terms with $k$ squarefree in $n/4 < k \leq n$ contribute independent square roots, and there are about $\frac34 n / \zeta(2)$ of these so the degree of $S(n)$ as an algebraic number grows exponentially in $n$.

One can, however, obtain a definite integral formula for $S(n)$ (indeed the OP's question suggested he or she started with such an integral): $$S(n) = -\frac1{\sqrt\pi} \int_0^\infty \left(1-e^{-x^2}\right)^n \frac{dx}{x^2}$$ for all $n>0$. (To obtain this formula, start with the familiar $\int_0^\infty e^{-ax^2} dx = \frac12 \sqrt{\pi/a}$, integrate from $a=0$ to $a=k$ and divide by $\sqrt\pi$ to obtain $$\sqrt{k} = \frac1{\sqrt\pi} \int_0^\infty \left(1-e^{-kx^2}\right) \frac{dx}{x^2},$$ and then multiply by $(-1)^k \binom{n}{k}$ and sum from $k=0$ to $k=n$.) For example, it follows from the integral that $$-1 = S(1) < S(2) < S(3) < S(4) < \cdots \rightarrow 0$$ but the convergence to zero is very slow, with $S(n)$ asymptotic to $-(\pi \log n)^{-1/2}$ for large $n$; for example $S(10^4)$ is still $-.1814\ldots\;$.$\$ [If numerical calculation suggests that $S(n)$ behaves more irregularly than this, beware of massive cancellation in the defining sum, whose largest terms are proportional to $\pm 2^n$; I used several thousand digits of precision to compute the numerical value of $S(10^4)$. At any rate it is clear that $S(n)<0$ for $n>0$, because it is $(-1)^n$ times an $n$-th finite difference of a function whose $n$-th derivative has sign $(-1)^{n+1}$ everywhere.]

• Indeed the exponent is $-kx^2$, not $-x^2$. Fixed now, thanks. – Noam D. Elkies Jun 4 '14 at 1:53
• (That acknowledges a typo correction from Barry Cipra, who then chose to delete his comment.) – Noam D. Elkies Jun 4 '14 at 4:43
• The formula $\int_0^\infty e^{-ax^2} = \frac12 \sqrt{\pi/2a}$ is wrong and must be: $\int_0^\infty e^{-ax^2}dx = \frac12 \sqrt{\pi/a}$ . – Han de Bruijn Jun 4 '14 at 14:13
• Thanks; I'll fix this too $-$ sorry for all the typos! – Noam D. Elkies Jun 4 '14 at 15:26
• @NoamD.Elkies a curiosity: how did you achieve several thousand digits of precision? – Ant Jun 4 '14 at 15:32

Here is some more information which also supports the assumption from Noam D.Elkies, that it is rather unlikely to find a simpler expression for the sum

$$S(n) = \sum_{k=0}^{n}\binom{n}{k}(-1)^k\sqrt{k}$$

We could try to simplify the sum using generating functions and transform the power series

$$\sum_{n\ge 0}S(n)z^n = \sum_{n\ge 0}\left(\sum_{k=0}^{n}\binom{n}{k}(-1)^k\sqrt{k}\right)z^n$$

with

Euler's series transformation formula:

Given a function $f(z)=\sum_{n\ge0}a_nz^n$ analytical on the unit disk, the following representation is valid: \begin{align} f(z)&=\sum_{n\ge0}a_nz^n\\ \frac{1}{1-z}f\left(\frac{z}{1-z}\right)&=\sum_{n\ge0}\left(\sum_{k=0}^{n}\binom{n}{k}a_k\right)z^n\tag{1} \end{align}

This transformation formula together with a proof using Cauchy's integral formula can be found in Harmonic Number Identities Via Euler's transform from Boyadzhiev ($2009$).

We observe that $a_n = (-1)^n\sqrt{n}$ and so we get the Polylogarithm $Li_{-\frac{1}{2}}(-z)$

$$f(z)=Li_{-\frac{1}{2}}(-z)=\sum_{n\ge1}\frac{(-z)^n}{n^{-\frac{1}{2}}}=\sum_{n\ge1}(-1)^n\sqrt{n}z^n$$

According to $(1)$ we see that $S(n)$ is the coefficient of $z^n$ from:

$$S(n)=\sum_{k=0}^{n}\binom{n}{k}(-1)^k\sqrt{k} = [z^n]\frac{1}{1+z}Li_{-\frac{1}{2}}\left(\frac{-z}{1+z}\right)$$

It' don't seem plausible (for me), that this polylogarithm could be properly transformed in order to retrieve a simpler expression for $S(n)$.