Csdrhrt

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+nchoose s+1} - {nchoose s+1}
= sum_{q=0}^s frac{m}{q+1}
{m+1+2qchoose q} {n-2-2qchoose 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.

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+nchoose s+1} - {nchoose s+1}
= sum_{q=0}^s frac{m}{q+1}
{m+1+2qchoose q} {n-2-2qchoose s-q}}$$

we observe that

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

Therefore we have two sums,

$$sum_{q=0}^s
{m+1+2qchoose q+1} {n-2-2qchoose s-q}
- sum_{q=0}^s
{m+1+2qchoose q} {n-2-2qchoose 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_{qge 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}-1right)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 {nchoose q} frac{1}{w^{s-q}}
= sum_{q=0}^s {nchoose q}
mathrm{Res}_{w=0} frac{1}{w^{s-q+2}} (1+w)^{m}
\ = sum_{q=0}^s {nchoose q} [w^{s-q+1}] (1+w)^m
= [w^{s+1}] (1+w)^m sum_{q=0}^s {nchoose q} w^q
\ = - {nchoose s+1}
+ [w^{s+1}] (1+w)^m sum_{q=0}^{s+1} {nchoose q} w^q.$$

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

$$- {nchoose s+1}
+ [w^{s+1}] (1+w)^m sum_{qge 0} {nchoose q} w^q
= - {nchoose s+1}
+ [w^{s+1}] (1+w)^{m+n}$$

This is

$$bbox[5px,border:2px solid #00A000]{
{m+nchoose s+1} - {nchoose 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 {nchoose q} w^{s-q}
= sum_{q=0}^s {nchoose 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.

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}^inftyleft(binom{m+1+2q}{q+1}-binom{m+1+2q}{q}right)binom{n-2-2q}{s-q}tag{1}\
&=sum_{q=0}^inftyleft([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)^qleft(frac{z}{(1+z)^2}right)^qtag{3}\
&=[w^0z^s]left(frac{1}{w}-1right)(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)^nfrac{1}{w(1+z)^2-(1+w)^2z}\
&=[w^0z^s](1-w)(1+w)^{m+1}(1+z)^nfrac{1}{wleft(1-frac{z}{w}right)(1-wz)}\
&=[w^0z^s](1-w)(1+w)^{m+1}(1+z)^nleft(frac{1}{wleft(1-w^2right)left(1-frac{z}{w}right)}right.\
&qquadqquadqquadqquadqquadqquadqquadqquadqquadleft.-frac{w}{left(1-w^2right)(1-wz)}right)tag{5}\
&=[w^0z^s](1+w)^{m}(1+z)^nleft(frac{1}{wleft(1-frac{z}{w}right)}-frac{w}{1-wz}right)tag{6}\
&=[w^1z^s](1+w)^{m}(1+z)^nfrac{1}{1-frac{z}{w}}\
&=[w^1](1+w)^msum_{j=0}^sbinom{n}{j}[z^{s-j}]sum_{k=0}^inftyleft(frac{z}{w}right)^ktag{7}\
&=[w^1](1+w)^msum_{j=0}^sbinom{n}{j}frac{1}{w^{s-j}}tag{8}\
&=[w^{s+1}](1+w)^mleft(sum_{j=0}^inftybinom{n}{j}w^j-sum_{j=s+1}^inftybinom{n}{j}w^jright)\
&=[w^{s+1}](1+w)^mleft((1+w)^n-sum_{j=s+1}^inftybinom{n}{j}w^jright)\
&,,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 $qto 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}^sfrac{m}{m+2j}binom{m+2j}{j}binom{n-2j}{s-j}tag{10}\
&=binom{n}{s}+sum_{j=1}^sfrac{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$.