5
$\begingroup$

I have a challenge for you combinatorial mathematicians. Is anyone willing to verify the following combinatorial identity?

$$\sum_{k=0}^n\sum_{j=0}^m\binom{m}{j}\binom{k-j}{p-j}\binom{p}{k-j}\binom{n+1}{k+m-j}$$ $$=\binom{n+1}{p}\binom{n+1}{m}-\binom{n+1-m}{p-m}\binom{p}{n+1-m}$$

Detailed steps or references would be appreciated. If this formula already resides in a long lost combinatorial book, I would love to know about it.

$\endgroup$
  • $\begingroup$ Did you try induction on $n$? $\endgroup$ – Greg Martin Feb 18 '14 at 1:36
2
$\begingroup$

After browsing through several combinatorial books, it seems that the notion I was looking for is called a Vandermonde identity. Hence, I can now provide a very simple proof.

We first note that $\binom{n+1-m}{p-m}\binom{p}{n+1-m}$ can be added to the summation, so that the indices range over all possible non-zero terms. Hence, disregarding the indices, we wish to show,

$$\sum_{k}\sum_{j}\binom{m}{j}\binom{k-j}{p-j}\binom{p}{k-j}\binom{n+1}{k+m-j}=\binom{n+1}{p}\binom{n+1}{m}.$$

We perform a substitution of $l=k-j$ on the left side and then apply two Vandermonde identities [Riordan, pp. 9, 15],

$\displaystyle\sum_{k}\sum_{j}\binom{m}{j}\binom{k-j}{p-j}\binom{p}{k-j}\binom{n+1}{k+m-j}$

\begin{align} \nonumber&=\sum_{l}\binom{p}{l}\binom{n+1}{m+l}\sum_{j}\binom{m}{j}\binom{l}{p-j} \\ \nonumber&=\sum_{l}\binom{p}{l}\binom{n+1}{m+l}\binom{m+l}{p} \\ \nonumber&=\sum_{l}\binom{p}{l-m}\binom{n+1}{l}\binom{l}{p} \\ \nonumber&=\sum_{l}\binom{l}{p}\binom{p}{l-m}\binom{n+1}{l} \\ \nonumber&=\binom{n+1}{p}\binom{n+1}{m}. \end{align}

$\endgroup$
  • $\begingroup$ You might try applying that approach to this more recent problem. (I've been trying to come up with a counting proof for it without any luck.) $\endgroup$ – Semiclassical Aug 2 '14 at 20:02

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.