3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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? $\endgroup$ – saulspatz Dec 23 '18 at 16:06
  • $\begingroup$ You have posted several different identities, replacing the previous one every time. It may be useful to make a list. $\endgroup$ – Marko Riedel Dec 23 '18 at 16:19
  • $\begingroup$ @MarkoRiedel Thank you so much. I made changes. I thought no one is working on this. I do really appreciate it. $\endgroup$ – induction601 Dec 23 '18 at 22:22
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – induction601 Dec 23 '18 at 23:14
  • 1
    $\begingroup$ I must refer you to Computation of combinatorial sums by G. P. Egorychev. $\endgroup$ – Marko Riedel Dec 24 '18 at 22:44
  • $\begingroup$ Thanks! I will read it $\endgroup$ – induction601 Dec 26 '18 at 19:32
  • $\begingroup$ And I would like to say thank you for your instructive answer. Your answer widens my perspective of combinatorics! $\endgroup$ – induction601 Dec 26 '18 at 19:39
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Marko Riedel Dec 25 '18 at 14:11
  • $\begingroup$ @MarkoRiedel: Many thanks for your nice comment. It's always a pleasure to learn from your posts. $\endgroup$ – Markus Scheuer Dec 25 '18 at 14:38
  • $\begingroup$ 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|$? $\endgroup$ – induction601 Dec 26 '18 at 19:32
  • $\begingroup$ In equation (7), it seems that it needs to be $\sum_{k=0}^\infty \left(\frac{z}{w}\right)^k$. $\endgroup$ – induction601 Dec 26 '18 at 19:35
  • $\begingroup$ @induction601: You're welcome. We work with formal power series and do not consider any convergence issues. Thanks for the hint, typo corrected. $\endgroup$ – Markus Scheuer Dec 26 '18 at 20:37

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.