# A combinatorial identity generalizing identity (3.111) from Gould's book

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.

• This question has now been answered: see math.stackexchange.com/questions/1145749/…. – Alex Isaev Feb 13 '15 at 1:22
• 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$. – Ira Gessel Feb 13 '15 at 3:02
• This question has been answered: see math.stackexchange.com/questions/1145749/… – Alex Isaev Feb 13 '15 at 4:31
• I'm wondering if this can be interpreted as an inclusion-exclusion summation. It looks like one. – 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.$$