# Verification of a Combinatorial Identity

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.

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

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}

• 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.) – Semiclassical Aug 2 '14 at 20:02