Identity involving difference of binomial coefficients

Question

I am trying to prove the following identity but not sure how to prove it.

[The followings are equivalent forms of the original equality I asked.] $$ \binom{m+n}{s+1} - \binom{n}{s+1} = \sum_{i=0}^s \frac{m}{s-i+1}\binom{m+1+2(s-i)}{s-i}\binom{n-2(s-i+1)}{i}. $$ $$ {m+n\choose s+1} - {n\choose s+1} = \sum_{q=0}^s \frac{m}{q+1} {m+1+2q\choose q} {n-2-2q\choose s-q} $$ $$ \binom{m+n}{s} = \sum_{i=0}^{s} \frac{m}{m+2i} \binom{m+2i}{i}\binom{n-2i}{s-i} $$

[Please ignore my attempt. It only explains one of equivalent forms.]

My attempt is to use the combinatorial argument. The lefthand side could be understood as follow. Suppose we have a box containing $m$ black balls and $n$ white balls. We randomly draw $s+1$ balls out of it. Then the LHS represents the number of ways that the selected $s+1$ balls.

However, not sure how to make a combinatorial argument on the RHS. Based on the RHS, the sum of all cases of drawing $s-i$ balls from somewhere and $i$ balls from white balls. But it is unclear to me to show the above identity.

Any suggestions/answers would be very appreciated. Thanks.

Answer 1

Remark. What follows answers one of several queries that appeared at this post, which each query replacing the previous one. We suggest making a list so that all the different varieties may be examined.

Starting from the claim

$$\bbox[5px,border:2px solid #00A000]{ {m+n\choose s+1} - {n\choose s+1} = \sum_{q=0}^s \frac{m}{q+1} {m+1+2q\choose q} {n-2-2q\choose s-q}}$$

we observe that

$${m+1+2q\choose q+1} - {m+1+2q\choose q} \\ = \frac{m+1+q}{q+1} {m+1+2q\choose q} - {m+1+2q\choose q} \\ = \frac{m}{q+1} {m+1+2q\choose q}.$$

Therefore we have two sums,

$$\sum_{q=0}^s {m+1+2q\choose q+1} {n-2-2q\choose s-q} - \sum_{q=0}^s {m+1+2q\choose q} {n-2-2q\choose s-q}.$$

For the first one we write

$$\sum_{q=0}^s [w^{q+1}] (1+w)^{m+1+2q} [z^{s-q}] (1+z)^{n-2-2q} \\ = \mathrm{Res}_{w=0} (1+w)^{m+1} [z^s] (1+z)^{n-2} \sum_{q=0}^s \frac{1}{w^{q+2}} z^q (1+w)^{2q} (1+z)^{-2q}.$$

We may extend $q$ beyond $s$ because of the coefficient extractor $[z^s]$ in front, getting

$$ \mathrm{Res}_{w=0} \frac{1}{w^2} (1+w)^{m+1} [z^s] (1+z)^{n-2} \sum_{q\ge 0} z^q w^{-q} (1+w)^{2q} (1+z)^{-2q} \\ = \mathrm{Res}_{w=0} (1+w)^{m+1} [z^s] (1+z)^{n-2} \frac{1}{w^2} \frac{1}{1-z(1+w)^2/w/(1+z)^2} \\ = \mathrm{Res}_{w=0} (1+w)^{m+1} [z^s] (1+z)^{n} \frac{1}{w} \frac{1}{w(1+z)^2-z(1+w)^2}.$$

Repeat the calculation for the second one to get

$$\mathrm{Res}_{w=0} (1+w)^{m+1} [z^s] (1+z)^{n} \frac{1}{w(1+z)^2-z(1+w)^2}.$$

Now we have

$$\left(\frac{1}{w}-1\right)\frac{1}{w(1+z)^2-z(1+w)^2} = \frac{1}{w-z} \frac{1}{w(1+w)} - \frac{1}{1-wz} \frac{1}{1+w} \\ = \frac{1}{1-z/w} \frac{1}{w^2(1+w)} - \frac{1}{1-wz} \frac{1}{1+w}.$$

We thus obtain two components, the first is

$$\mathrm{Res}_{w=0} (1+w)^{m+1} [z^s] (1+z)^{n} \frac{1}{1-z/w} \frac{1}{w^2(1+w)} \\ = \mathrm{Res}_{w=0} \frac{1}{w^2} (1+w)^{m} [z^s] (1+z)^{n} \frac{1}{1-z/w} \\ = \mathrm{Res}_{w=0} \frac{1}{w^2} (1+w)^{m} \sum_{q=0}^s {n\choose q} \frac{1}{w^{s-q}} = \sum_{q=0}^s {n\choose q} \mathrm{Res}_{w=0} \frac{1}{w^{s-q+2}} (1+w)^{m} \\ = \sum_{q=0}^s {n\choose q} [w^{s-q+1}] (1+w)^m = [w^{s+1}] (1+w)^m \sum_{q=0}^s {n\choose q} w^q \\ = - {n\choose s+1} + [w^{s+1}] (1+w)^m \sum_{q=0}^{s+1} {n\choose q} w^q.$$

We may extend $q$ beyond $s+1$ due to the coefficient extractor in front, to get

$$- {n\choose s+1} + [w^{s+1}] (1+w)^m \sum_{q\ge 0} {n\choose q} w^q = - {n\choose s+1} + [w^{s+1}] (1+w)^{m+n}$$

This is

$$\bbox[5px,border:2px solid #00A000]{ {m+n\choose s+1} - {n\choose s+1}.}$$

We have the claim, so we just need to prove that the second component will produce zero. We obtain

$$\mathrm{Res}_{w=0} (1+w)^{m+1} [z^s] (1+z)^{n} \frac{1}{1-wz} \frac{1}{1+w} \\ = \mathrm{Res}_{w=0} (1+w)^{m} [z^s] (1+z)^{n} \frac{1}{1-wz} \\ = \mathrm{Res}_{w=0} (1+w)^{m} \sum_{q=0}^s {n\choose q} w^{s-q} = \sum_{q=0}^s {n\choose q} \mathrm{Res}_{w=0} w^{s-q} (1+w)^{m} = 0.$$

This concludes the argument. Having reached the end of the computation we observe that we did not require the full mechanics of the complex residue and a coefficient extractor would have sufficed.

Answer 2

This is a mere supplement to @MarkoRiedel's instructive answer slightly streamlining a few steps.

We obtain \begin{align*} \color{blue}{\sum_{q=0}^s}&\color{blue}{\frac{m}{q+1}\binom{m+1+2q}{q}\binom{n-2-2q}{s-q}}\\ &=\sum_{q=0}^\infty\left(\binom{m+1+2q}{q+1}-\binom{m+1+2q}{q}\right)\binom{n-2-2q}{s-q}\tag{1}\\ &=\sum_{q=0}^\infty\left([w^{q+1}]-[w^q]\right)(1+w)^{m+1+2q}[z^{s-q}](1+z)^{n-2-2q}\tag{2}\\ &=\left([w^1]-[w^0]\right)(1+w)^{w+1}[z^s](1+z)^{n-2}\sum_{q=0}^\infty \left(\frac{(1+w)^2}{w}\right)^q\left(\frac{z}{(1+z)^2}\right)^q\tag{3}\\ &=[w^0z^s]\left(\frac{1}{w}-1\right)(1+w)^{m+1}(1+z)^{n-2}\frac{1}{1-\frac{(1+w)^2z}{w(1+z)^2}}\tag{4}\\ &=[w^0z^s](1-w)(1+w)^{m+1}(1+z)^n\frac{1}{w(1+z)^2-(1+w)^2z}\\ &=[w^0z^s](1-w)(1+w)^{m+1}(1+z)^n\frac{1}{w\left(1-\frac{z}{w}\right)(1-wz)}\\ &=[w^0z^s](1-w)(1+w)^{m+1}(1+z)^n\left(\frac{1}{w\left(1-w^2\right)\left(1-\frac{z}{w}\right)}\right.\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\left.-\frac{w}{\left(1-w^2\right)(1-wz)}\right)\tag{5}\\ &=[w^0z^s](1+w)^{m}(1+z)^n\left(\frac{1}{w\left(1-\frac{z}{w}\right)}-\frac{w}{1-wz}\right)\tag{6}\\ &=[w^1z^s](1+w)^{m}(1+z)^n\frac{1}{1-\frac{z}{w}}\\ &=[w^1](1+w)^m\sum_{j=0}^s\binom{n}{j}[z^{s-j}]\sum_{k=0}^\infty\left(\frac{z}{w}\right)^k\tag{7}\\ &=[w^1](1+w)^m\sum_{j=0}^s\binom{n}{j}\frac{1}{w^{s-j}}\tag{8}\\ &=[w^{s+1}](1+w)^m\left(\sum_{j=0}^\infty\binom{n}{j}w^j-\sum_{j=s+1}^\infty\binom{n}{j}w^j\right)\\ &=[w^{s+1}](1+w)^m\left((1+w)^n-\sum_{j=s+1}^\infty\binom{n}{j}w^j\right)\\ &\,\,\color{blue}{=\binom{m+n}{s+1}-\binom{n}{s+1}}\tag{9} \end{align*} and the claim follows.

The essential steps are (1) where we get rid of the denominator by using a representation as difference of binomial coefficients and the partial fraction decomposition in (5).

Comment:

• In (1) we use the binomial identity $\frac{m}{q+1}\binom{m+1+2q}{q}=\binom{m+1+2q}{q+1}-\binom{m+1+2q}{q}$.

• In (2) we apply the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series.

• In (3) we use the linearity of the coefficient of operator and apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

• In (4) we use the geometric series expansion and apply again the rule from (3).

• In (5) we do a partial fraction expansion.

• In (6) we observe the right term $\frac{w}{1-wz}=w+w^2z+w^3z^2+\cdots$ can be skipped, since there is no contribution to $[w^0]$.

• In (7) we do again a geometric series expansion and expand the binomial.

• In (8) we select the coefficient of $z^{s-j}$.

• In (9) we select the coefficient of $w^{s+1}$.

OPs first identity:

The right-hand side of the first identity follows from the right-hand side of the second by reversing the order of summation $q\to s-q$.

OPs third identity:

We obtain \begin{align*} \color{blue}{\sum_{j=0}^s}&\color{blue}{\frac{m}{m+2j}\binom{m+2j}{j}\binom{n-2j}{s-j}}\\ &=\binom{n}{s}+\sum_{j=1}^s\frac{m}{m+2j}\binom{m+2j}{j}\binom{n-2j}{s-j}\tag{10}\\ &=\binom{n}{s}+\sum_{j=1}^s\frac{m}{j}\binom{m+2j-1}{j-1}\binom{n-2j}{s-j}\tag{11}\\ &=\binom{n}{s}+\sum_{j=0}^{s-1}\frac{m}{j+1}\binom{m+1+2j}{j}\binom{n-2-2j}{s-1-j}\tag{12}\\ &=\binom{n}{s}+\binom{m+n}{s}-\binom{n}{s}\tag{13}\\ &\,\,\color{blue}{=\binom{m+n}{s}} \end{align*}

Comment:

• In (10) we separate the first summand with $j=0$.

• In (11) we use the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

• In (12) we shift the index and start with $j=0$.

• In (13) we apply (9) by substituting $s$ with $s-1$.