8
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ This question has now been answered: see math.stackexchange.com/questions/1145749/…. $\endgroup$
    – Alex Isaev
    Commented Feb 13, 2015 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
    Commented Feb 13, 2015 at 3:02
  • $\begingroup$ This question has been answered: see math.stackexchange.com/questions/1145749/… $\endgroup$
    – Alex Isaev
    Commented Feb 13, 2015 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
    Commented Feb 13, 2015 at 5:03

1 Answer 1

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .