16
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Phira Apr 21 '13 at 21:15
  • $\begingroup$ @Phira That's a good question. The sum seems to behave pretty weirdly from my numerical calculations. $\endgroup$ – Alexander Gruber May 18 '14 at 1:29
  • $\begingroup$ 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). $\endgroup$ – Jack M Jun 2 '14 at 21:14
15
+150
$\begingroup$

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.]

$\endgroup$
  • $\begingroup$ Indeed the exponent is $-kx^2$, not $-x^2$. Fixed now, thanks. $\endgroup$ – Noam D. Elkies Jun 4 '14 at 1:53
  • $\begingroup$ (That acknowledges a typo correction from Barry Cipra, who then chose to delete his comment.) $\endgroup$ – Noam D. Elkies Jun 4 '14 at 4:43
  • $\begingroup$ 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}$ . $\endgroup$ – Han de Bruijn Jun 4 '14 at 14:13
  • $\begingroup$ Thanks; I'll fix this too $-$ sorry for all the typos! $\endgroup$ – Noam D. Elkies Jun 4 '14 at 15:26
  • $\begingroup$ @NoamD.Elkies a curiosity: how did you achieve several thousand digits of precision? $\endgroup$ – Ant Jun 4 '14 at 15:32
5
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.