# partial alternating sum involving binomial coefficients

I came across the following alternating sum $$\sum_{k=0}^n (-1)^k \binom{2n}{k} (n-k)^r,\quad 1\leq r < n.$$ It seems that when $$r$$ is an even integer the sum is $$0$$ and when $$r$$ is an odd integer the sum is not zero (regardless of the parity of $$n$$).

[Edited] The case when $$r$$ is even is easy by symmetry as Darij Grinberg pointed out below. So the question left is how to show that the sum is nonzero when $$r$$ is odd.

The main difficulty I have proving this is that the sum is only from $$0$$ to $$n$$ instead of to $$2n$$, and I don't see how to apply the classical methods such as finite differences, integral representation, series, etc.

• Oh. I'm pretty sure you can just extend this sum to $k=0$ to $2n$ by doubling it (for symmetry reasons). And then it should follow from finite differences. – darij grinberg Oct 14 '18 at 23:36
• The sum from $k=0$ to $n$ and the corresponding sum from $k=n$ to $2n$ are equal, because $\left(n-k\right)^r = \left(n-\left(2n-k\right)\right)^r$ (since $r$ is even) and $\dbinom{2n}{k} = \dbinom{n}{2n-k}$ and $\left(-1\right)^k = \left(-1\right)^{2n-k}$. – darij grinberg Oct 14 '18 at 23:41
• @darijgrinberg I see, thanks! How do you show that the sum is not zero if $r$ is not even? – user58955 Oct 14 '18 at 23:52
• Oh, that isn't a consequence of anything I did, and I don't know how to show it. I thought you were just mentioning it as a limitation of your claim. – darij grinberg Oct 14 '18 at 23:53
• My proof that the sum is $0$ when $r$ is even can now be found in full detail in the solutions to UMN Fall 2018 Math 4707 Homework #4 (where the claim appears as Exercise 6 (b)). – darij grinberg Nov 4 '18 at 2:11

## 4 Answers

In a post on Math Stack Exchange, MSE 2827591, I prove the following:

$$\sum_{k=1}^n (-1)^{k+1} \binom{2n}{n+k} k^s = \binom{2n}{n} \sin(\pi s/2) \int_0^\infty \frac{dx \, \,x^s}{\sinh{\pi x}} \frac{n!^2}{(n+ix)!(n-ix)!}.$$

The OP's formula can be put in the form on the LHS of this equation. By inspection the questions of concern can be answered; namely, the value of zero for $$s$$ an even integer, and non-zero otherwise.

• Thanks! The equation [2] in that post of yours is already enough. – user58955 Oct 15 '18 at 5:21
• what is $(n+ix)!$? – Fedor Petrov Oct 15 '18 at 7:06
• @FedorPetrov I think it means $\Gamma(n+ix+1)$ – user58955 Oct 15 '18 at 8:24
• @user58955 I thought about it, but that text contains also Gamma-function notation, why use both? It looks confusing. – Fedor Petrov Oct 15 '18 at 9:51

Just for the curious mind.

Let's suppose $$r\rightarrow 2r+1$$. Then, the constant term in Brendan McKay's experiment can be given as follows: $$\frac{2(-1)^{r-1}(2r+1)!B(2r)}{r!\,2^r}$$ where $$B(n)$$ are the Bernoulli numbers.

Here's a very clunky approach that might not be close to a general solution. However, it is a proof for $$r\le 99$$. Define $$p_r(n)$$ by $$\sum_{k=0}^n (-1)^k \binom {2n}k (n-k)^r = (-1)^n\binom{2n}{n}\frac{n^2\,p_r(n)}{2\prod_{t=0}^{(r-1)/2} (2n-2t+1)}.$$

For $$r=3,5,\ldots,99$$, $$p_r(n)$$ is a polynomial of degree $$\frac{r-3}2$$ with integer coefficients.

For example $$p_3(n) = 1$$, $$p_5(n)=-4n+1$$, $$p_7(n)=34n^2-24n+5$$.

For odd $$r\le 99$$, $$p_r(n)$$ is irreducible, but that is likely to be very hard to prove (or false) for all $$r$$. A simpler observation is that, for $$r\le 99$$, all the coefficients of $$p_r(n)$$ are even, except that the constant term is odd. Therefore, $$p_r(n)$$ is an odd integer when $$n$$ is an integer.

Without caring about its coefficients, maybe there is a direct way to show that $$p_r(n)$$ is odd whenever $$r$$ is odd.

• How did you find that the non-constant terms in $p_r(n)$ have even coefficients? With computer aid? – user58955 Oct 15 '18 at 2:55
• I used Maple. It took about 10 mins to get up to $r=99$. – Brendan McKay Oct 15 '18 at 4:38

There is already a fine answer. Here are a few comments and generalizations that might lead to another. Together they are slightly redundant but I don't know which (if any) would work best.

Along with the given sum $$f(n,r)=\sum_{k=0}^{n} (-1)^k \binom{2n}{k} (n-k)^r$$ consider also $$g(n,r)=\sum_{k=0}^{2n} (-1)^k \binom{2n}{k}(n-k)^r.$$

The observation (ignoring the part about odd $$r$$) is that, seemingly,

$$f(n,r)=0$$ for even $$1 \le r \lt n.$$

Here is a claim which looks nicer although it is really no stronger and no weaker:

$$g(n,r)=0$$ for $$0 \le r \lt n.$$

The reason the two are the same (aside from the well known case of $$r=0$$) is that for odd $$r,$$ $$g(n,r)=f(n,r)-f(n,r)$$ for odd $$r$$ and for even $$r$$ $$g(n,r)=f(n,r)+f(n,r)+(-1)^n\binom{2n}{n}0^r.$$

However there might be a nice proof for all $$r$$ which ignores the easier cancellation for odd $$r.$$

Also, we will note below that "$$(n-k)^r$$ for $$r \lt N$$" can be replaced by "$$p(k)$$ for any polynomial $$p(t)$$ of degree less than $$N.$$"

The bounds on $$r$$ are more restrictive than needed. Computations leave one highly confident that

$$f(n,r)=0$$ for even $$1 \le r \lt 2n.$$

Equivalently

$$g(n,r)=0$$ for $$0 \le r \lt 2n.$$

of course for the rather trivial reason $$g(n,r)=0$$ for any odd $$r.$$

Since the functions $$t^0,t^1,\cdots,t^{2n-1}$$ are a basis for the space $$P_{2n-1}(t)$$ of polynomials of degree less than $$2n,$$ the last claim that

$$\sum_{k=0}^{2n} (-1)^k \binom{2n}{k}(n-k)^r=0$$ for $$0 \le r \lt 2n$$

is equivalent to

$$\sum_{k=0}^{2n} (-1)^k \binom{2n}{k}p(n-k)=0$$ for all $$p \in P_{2n-1}(t)$$

and hence also to

$$\sum_{k=0}^{2n} (-1)^k \binom{2n}{k}q(k)=0$$ for all $$q \in P_{2n-1}(t)$$

This fits in nicely with the remark about finite differences.

Using a different basis

$$\sum_{k=0}^{2n} (-1)^k \binom{2n}{k}\binom{k}{r}=0$$ for $$0 \le r \lt 2n.$$

Now consider for a polynomial $$p=p(t)$$ the sum

$$G(N,p)=\sum_{k=0}^{N} (-1)^k \binom{N}{k}p(k).$$

The previous claim

$$g(n,r)=G(2n,(n-t)^r)=0$$ for $$0 \le r \lt 2n$$

which , as explained, is equivalent to

$$G(2n,p(k))=0$$ for any $$p\in P_{2n-1}$$

Does not depend on the bound being even:

$$G(N,p(k))=0$$ for any $$p \in P_{N-1}$$

Finally, here is another perspective which follows from (and imples) some of the above. Consider the polynomials

$$h_{n,r}(t)=\sum_{k=0}^{n} t^k \binom{2n}{k}(n-k)^r.$$

The starting claim was

For even $$1 \lt r \lt 2n,$$ $$h_{n,r}(-1)=0$$ i.e. $$(t+1)$$ divides $$h_{n,r}.$$

In fact

$$(t+1)^{2n-r}$$ divides $$h_{n,r}.$$

Again, the moves of changing to $$\sum_{k=0}^{2n} t^k \binom{2n}{k}(n-k)^r$$ and then $$\sum_{k=0}^{N} t^k \binom{N}{k}p(k)$$ are possible with the last thing being divisible by $$(t+1)^{N-r}$$ where $$r \leq N$$ is the degree of $$p(t).$$