Identity for Difference of Sum of Products of Binomial Coefficients

Question

Problem Statement

I recently came across the following equation that I want to prove:

$$ \sum_{i=1}^{n} \left[ \binom{n+i}{m}-\binom{n-i}{m} \right] \binom{2n}{n-i} = \sum_{i=1}^{m}\binom{n+i}{m}\binom{2n}{n-i} $$

My Attempt

Simply subtracting RHS from LHS and using $\binom{2n}{n-i}=\binom{2n}{n+i}$, I got the following equation:

$$ \sum_{i=m+1}^{n}\binom{n+i}{m}\binom{2n}{n+i} - \sum_{i=1}^{n}\binom{n-i}{m}\binom{2n}{n-i} = 0 $$

Say we wish to color $2n$ distinct balls such that $m$ of them are pink, some of them (can be none) are white, and the rest (can be none) black. The terms on LHS are, respectively (without the negative sign)

1. The number of colouring such that at least $n+1$ of the balls are black
2. The number of colouring such that at most $n-m-1$ of the balls are white

These two are equal, so their difference is zero and the equation is proved.

Question

Looking for help to verify this proof. Also, is there a more elegant proof e.g. with another combinatorial proof, induction, generating functions, etc.?

Answer 1

We show the following is valid for $0\leq m<n$ \begin{align*} \color{blue}{\sum_{i=m+1}^n\binom{n+i}{m}\binom{2n}{n+i}=\sum_{i=1}^n\binom{n-i}{m}\binom{2n}{n-i}}\tag{1} \end{align*}

We start with the right-hand side of (1) and obtain \begin{align*} \color{blue}{\sum_{i=1}^n\binom{n-i}{m}\binom{2n}{n-i}} &=\sum_{i=1}^{n-m}\binom{n-i}{m}\binom{2n}{n-i}\tag{2}\\ &=\sum_{i=m+1}^{n}\binom{n+m-i}{m}\binom{2n}{n+m-i}\tag{3}\\ &\,\,\color{blue}{=\sum_{i=m+1}^{n}\binom{n+i}{m}\binom{2n}{n+i}}\tag{4} \end{align*} and the claim (1) follows.

Comment:

• In (2) we note that $\binom{p}{q}=0$ if $0\leq p < q$ so that $n-i\geq m$ from which $i\leq n-m$ follows.

• In (3) we shift the index to start with $m+1$.

• In (4) we use the binomial identity \begin{align*} \binom{n+m-i}{m}\binom{2n}{n+m-i}&=\frac{(n+m-i)!}{m!(n-i)!}\,\frac{(2n)!}{(n+m-i)!(n-m+i)!}\\ &=\frac{(n+i)!}{m!(n-i)!}\,\frac{(2n)!}{(n+i)!(n-m+i)!}\\ &=\binom{n+i}{m}\binom{2n}{n+i} \end{align*}

Answer 2

Your proof is OK, but there are some things you could improve:

It’s perhaps worth explaining how it is that the two sums count the same thing in much the same way, and thus should have the same number of terms, but don’t. This is because the terms in the second sum with $n-i\lt m$ are zero; you could change the summation to run from $1$ to $n-m$ to make it apparent that it has the same number of terms as the first sum.

And to make it a bit easier to understand you could explain that on the left you first pick pink and black from all balls, then pink from pink and black whereas on the right you first pick pink and white from all balls and then pink from pink and white.

(I kept writing “punk” instead of “pink” – apparently my fingers know that I like punk and I don’t like pink :-)