# Identity involving difference of binomial coefficients

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.

• "Then the LHS represents the number of ways that the selected s+1 balls." I don't understand this. Is something missing from this sentence? – saulspatz Dec 23 '18 at 16:06
• You have posted several different identities, replacing the previous one every time. It may be useful to make a list. – Marko Riedel Dec 23 '18 at 16:19
• @MarkoRiedel Thank you so much. I made changes. I thought no one is working on this. I do really appreciate it. – induction601 Dec 23 '18 at 22:22

## 2 Answers

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.

• Could you add a bit more detailed explanation? Not sure where $\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}$ comes from. – induction601 Dec 23 '18 at 23:14
• I must refer you to Computation of combinatorial sums by G. P. Egorychev. – Marko Riedel Dec 24 '18 at 22:44
• Thanks! I will read it – induction601 Dec 26 '18 at 19:32
• And I would like to say thank you for your instructive answer. Your answer widens my perspective of combinatorics! – induction601 Dec 26 '18 at 19:39

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$$.

• This is very nice work. I was going to do the re-write myself and then I thought you might want to contribute here. We now have a complete page. Upvoted. – Marko Riedel Dec 25 '18 at 14:11
• @MarkoRiedel: Many thanks for your nice comment. It's always a pleasure to learn from your posts. – Markus Scheuer Dec 25 '18 at 14:38
• Thanks for such a nice work. In (4), how do we know the geometric series converges? Are we assuming $|(1+w)^2/w| < |(1+z)^2/z|$? – induction601 Dec 26 '18 at 19:32
• In equation (7), it seems that it needs to be $\sum_{k=0}^\infty \left(\frac{z}{w}\right)^k$. – induction601 Dec 26 '18 at 19:35
• @induction601: You're welcome. We work with formal power series and do not consider any convergence issues. Thanks for the hint, typo corrected. – Markus Scheuer Dec 26 '18 at 20:37