In my work I've come across the interesting binomial identity $$ \sum_{n\geq k} \frac{\binom{n}{k}}{\binom{m-1}{k}} \frac{\binom{m-1}{n} \binom{i-m-1}{j-n-1}}{\binom{i-2}{j-1}} = \frac{\binom{j-1}{k}}{\binom{i-2}{k}}. $$

That is, for some non-negative integer $k$ and hypergeometrically-distributed $n$, the expected value of $\binom{n}{k}/\binom{m-1}{k}$ has this form.

I'm sure it will fall to a tedious inductive proof or some generating function technique, but I was wondering if anybody knew of (a) a source that describes this identity or (b) a slick combinatorial or counting proof of such a statement?


Note that $$ \frac{\binom{n}{k}}{\binom{m-1}{k}}\binom{m-1}{n} =\frac{ (m-k-1)!}{(n-k)!(m-1-n)!}=\binom{m-k-1}{n-k} $$ Thus $$\eqalign{ \sum_{n\geq k}\frac{\binom{n}{k}}{\binom{m-1}{k}}\binom{m-1}{n}\binom{i-m-1}{j-n-1} &=\sum_{p\geq0}\binom{m-k-1}{p}\binom{i-m-1}{j-k-1-p}\cr &=\binom{i-k-2}{j-k-1} } $$ Where we used the fact that $$ \sum_{p\geq0}\binom{a}{p}\binom{b}{c-p}=\binom{a+b}{c} $$ Since this is the coefficient of $X^c$ in the product $(1+X)^a(1+X)^b$. The final step is to note that $$ \frac{\binom{i-k-2}{j-k-1}}{\binom{i-2}{j-1}}= \frac{\binom{j-1}{k}}{\binom{i-2}{k}} $$ which is straightforward.$\qquad\square$

  • $\begingroup$ Nice! Embarrassingly straight-forward, thanks for looking at it. $\endgroup$ – Jason Jun 30 '14 at 18:07

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.