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$
5
  • 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$ Commented Oct 14, 2018 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$ Commented Oct 14, 2018 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
    Commented Oct 14, 2018 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$ Commented Oct 14, 2018 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$ Commented Nov 4, 2018 at 2:11

4 Answers 4

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$
4
  • $\begingroup$ Thanks! The equation [2] in that post of yours is already enough. $\endgroup$
    – user58955
    Commented Oct 15, 2018 at 5:21
  • $\begingroup$ what is $(n+ix)!$? $\endgroup$ Commented Oct 15, 2018 at 7:06
  • $\begingroup$ @FedorPetrov I think it means $\Gamma(n+ix+1)$ $\endgroup$
    – user58955
    Commented Oct 15, 2018 at 8:24
  • $\begingroup$ @user58955 I thought about it, but that text contains also Gamma-function notation, why use both? It looks confusing. $\endgroup$ Commented Oct 15, 2018 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$
2
  • $\begingroup$ How did you find that the non-constant terms in $p_r(n)$ have even coefficients? With computer aid? $\endgroup$
    – user58955
    Commented Oct 15, 2018 at 2:55
  • $\begingroup$ I used Maple. It took about 10 mins to get up to $r=99$. $\endgroup$ Commented Oct 15, 2018 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 and acknowledge you have read our privacy policy.

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