I am trying to prove the following identity, which I am sure is correct: $$ \sum_{m=0}^{K}(-1)^m{n \choose m}{(n-m)r-1 \choose n-1}=1, $$ where $K:=\left[n\frac{r-1}{r}\right]$ for some integer $r$, and $[x]$ denotes the largest integer contained in $x$.

In the special case $r=2$ this is identity (3.111) from H. Gould's book "Combinatorial identities" (1972). For $r=2$ it was first stated by B. C. Wong in Amer. Math. Monthly in May 1930 as an open question. I am wondering if someone has seen a proof of (or can prove) this identity for any $r$. The upper summation limit$\left[n\frac{r-1}{r}\right]$ also occurs in Gould's book in identity (3.113), so it is not entirely unheard of.

  • 1
    $\begingroup$ This question has now been answered: see math.stackexchange.com/questions/1145749/…. $\endgroup$ – Alex Isaev Feb 13 '15 at 1:22
  • 5
    $\begingroup$ If we change the upper limit of the sum to $n$ then the sum is the $n$th difference of a polynomial of degree $n-1$ and is therefore 0. The only nonzero term in the extended sum not in the restricted sum is $-1$, corresponding to $m=n$. $\endgroup$ – Ira Gessel Feb 13 '15 at 3:02
  • $\begingroup$ This question has been answered: see math.stackexchange.com/questions/1145749/… $\endgroup$ – Alex Isaev Feb 13 '15 at 4:31
  • 1
    $\begingroup$ I'm wondering if this can be interpreted as an inclusion-exclusion summation. It looks like one. $\endgroup$ – Brendan McKay Feb 13 '15 at 5:03

As Brendan McKay commented, this looks like inclusion-exclusion. I just happened to write up such an inclusion-exclusion.

Suppose we want to count the number of ways to roll a total of $t$ on $n$ $r$-sided dice (with sides $1, 2, ..., r$). By inclusion-exclusion (or, via generating functions, by using the binomial theorem twice to expand the powers in $[x^t](x^n (x^r-1)^n (x-1)^{-n}$), this is

$$\sum_{m=0}^{[(t-n)/r]} (-1)^m {n \choose m}{t-1 - m r \choose n-1}.$$

Choose $t=nr$. There is just one way to roll a total of $nr$, by getting the maximum $r$ on each of the $n$ dice. So,

$$\sum_{m=0}^{[(n(r-1)/r]} (-1)^m {n \choose m}{(n-m)r-1 \choose n-1}=1.$$


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.