5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – darij grinberg Oct 14 '18 at 23:36
  • $\begingroup$ 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}$. $\endgroup$ – darij grinberg Oct 14 '18 at 23:41
  • $\begingroup$ @darijgrinberg I see, thanks! How do you show that the sum is not zero if $r$ is not even? $\endgroup$ – user58955 Oct 14 '18 at 23:52
  • $\begingroup$ 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. $\endgroup$ – darij grinberg Oct 14 '18 at 23:53
  • $\begingroup$ 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)). $\endgroup$ – darij grinberg Nov 4 '18 at 2:11
4
$\begingroup$

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.

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

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.

$\endgroup$
1
$\begingroup$

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.

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

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

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