# An identity involving binomial coefficients

Prove the following identity $$\displaystyle \sum_{i+j=m}\frac{(n-1) \binom{ai+n-1}{i} \binom{aj+1}{j}}{(ai+n-1)(aj+1)} = \frac{n\binom{am+n}{m}}{am+n}$$ where $i = 0,1,\cdots,m$ and $m, n$ are positive integers and $a$ is a positive integer or even a fraction.

One complete proof can be found in that famous book "Concrete Mathematics" by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik which is widely used as a textbook in many computer science departments.

Another complete proof can be found in the book written by Egorychev which is directly using the inversion rule of residue, see page 49 in the book "Integral representation and the computation of combinatorial sums". If you are reading that book, keep in mind that the index under $\sum$ can be extended to infinity because the contour integral has no pole when $k>n$.

• okay, I know how to prove this, it can be proved using the inversion rule of residue, see page 49 Integral representation and the computation of combinatorial sums – Pew Jan 21 '16 at 1:34
• Please don't destroy your question. Others may find it and its answer useful. – Robert Israel Jan 25 '16 at 18:51

This is a nice example to apply the inversion rule of formal power series stated as rule 4 in G.P. Egorychevs Integral Representations and the Computation of Combinatorial Sums section 1.2.2.

I think it's worthwhile to present a complete proof. Here we use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a formal power series. We show

The following is valid for $m,n\geq 1$ and $a\in\mathbb{R}$ appropriate \begin{align*} \sum_{{i+j=m}\atop{i,j\geq 0}}&\frac{n-1}{ai+n-1}\binom{ai+n-1}{i}\frac{1}{aj+1}\binom{aj+1}{j} =\frac{n}{am+n}\binom{am+n}{m} \end{align*}



Comment:

• In (1) we use the identity $$\frac{q}{pk+q}\binom{pk+q}{k}=\binom{pk+q}{k}-p\binom{pk+q-1}{k-1}$$ We also set the upper limit of the sum to $\infty$ without changing anything since we are only adding zero.

• In (2) we rearrange the sum, use the linearity of the coefficient of operator and the rule $[z^{n-k}]A(z)=[z^n]z^kA(z)$.

• In (3) we use the inversion rule

\begin{align*} \sum_{i=0}^\infty w^i [z^i]A(z)f^i(z)=\left.\left(A(z)\frac{f(z)}{f(z)-zf^{\prime}(z)}\right)\right|_{z=g(w)} \end{align*} with $g(w)$ the inverse of $w=\frac{z}{g(z)}$. We get from (2) \begin{align*} A(z)&=(1+z)^{n-2}(1+z-az)\\ f(z)&=(1+z)^a \end{align*} and obtain \begin{align*} A(z)\frac{f(z)}{f(z)-zf^{\prime}(z)}&=(1+z)^{n-2}(1+z-az)\frac{(1+z)^a}{(1+z)^a-az(a+z)^{a-1}}\\ &=(1+z)^{n-1} \end{align*} Since $w=\frac{z}{f(z)}=\frac{z}{(1+z)^a}$ we apply in (3) the substitution $z=w$.

• (+1). Upvoted. I congratulate you on presenting this difficult material from the canonical text. I had not used the inversion rule because the proof of this rule as found in the book requires more machinery than what can be presented in a MSE post. Reading your computation I have now found a rigorous proof of these identities by a simple substitution which you may find above. It relies on formal power series identities only and makes no assumptions about the trajectories of the poles of a bivariate complex function. – Marko Riedel Jan 25 '16 at 5:43
• @MarkoRiedel: Thanks for your nice comment and +1 for your updated answer. I've already upvoted your other answer some days before. Btw, I appreciate your Wikipedia articles. The last one about Egorychevs Method with this nice ref to your example collection is worth a detailed reading! Thanks! :-) – Markus Scheuer Jan 25 '16 at 7:57
• Apparently G. P. Egorychev does not have a biographical entry in English at Wikipedia. Do you know if his biography is somewhere on the internet in a major European language and preferably under the license that Wikipedia uses? – Marko Riedel Jan 25 '16 at 18:05
• @MarkoRiedel: Regrettably I can't provide you with helpful information. In the course of his 70th birthday in 2008, Springer published Advances in Combinatorial Mathematics which contains contributions in honor of Egorychev. Maybe you can retrieve information about him from one of the contributors.If so, I'm also keen to get some information about his life. Best regards, – Markus Scheuer Jan 26 '16 at 14:03
• @MarkusScheuer there is a $n$ missing at the RHS numerator of the starting identity, same at the numerator of the very last one (it should be as in the first dot of the comment), but otherwise the demonstration is correct and very interesting as for the method applied. And, concerning the definition field, actually $a$ could be also complex, and same $n$ (apart $1$), while $m$ can be also $0$ (when $n \ne 0,1$). – G Cab May 14 '16 at 15:06

What follows is only a partial answer.

Suppose we seek to verify that

$$\sum_{q=0}^m \frac{1}{aq+n-1} \frac{1}{am+1-aq} {aq+n-1\choose q} {am+1-aq\choose m-q} \\ = \frac{n}{n-1} \frac{1}{am+n} {am+n\choose m}.$$

Now observe that $$\frac{1}{aq+n-1} \frac{1}{am+1-aq} = \frac{1}{am+n} \frac{1}{aq+n-1} + \frac{1}{am+n} \frac{1}{am+1-aq}.$$

The identity now becomes

$$\sum_{q=0}^m \frac{1}{aq+n-1} {aq+n-1\choose q} {am+1-aq\choose m-q} \\ + \sum_{q=0}^m \frac{1}{am+1-aq} {aq+n-1\choose q} {am+1-aq\choose m-q} \\ = \frac{n}{n-1} {am+n\choose m}.$$

Call the two pieces appearing here $S_1$ and $S_2$ and start with $S_1.$ Now we have

$${aq+n-1\choose q} = \frac{aq+n-1}{q} {aq+n-2\choose q-1}$$

so that $${aq+n-1\choose q} - a {aq+n-2\choose q-1} = \frac{n-1}{q} {aq+n-2\choose q-1} \\ = \frac{n-1}{aq+n-1} {aq+n-1\choose q}.$$

Substituting this into $S_1$ yields

$$\frac{1}{n-1} \sum_{q=0}^m {aq+n-1\choose q} {am+1-aq\choose m-q} \\ - a \frac{1}{n-1} \sum_{q=0}^m {aq+n-2\choose q-1} {am+1-aq\choose m-q}.$$

There are two pieces here call them $T_{11}$ and $T_{12}.$

For $T_{11}$ introduce the integrals $${aq+n-1\choose q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{aq+n-1}}{z^{q+1}} \; dz$$

and

$${am+1-aq\choose m-q} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+1-aq}}{w^{m-q+1}} \; dw$$

The second of these controls the range so we may extend $q$ to infinity to get

$$\frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+1}}{w^{m+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-1}}{z} \sum_{q\ge 0} \frac{w^q}{z^q} \frac{(1+z)^{aq}}{(1+w)^{aq}} \; dz\; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+1}}{w^{m+1}} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-1}}{z} \frac{1}{1-w(1+z)^a/z/(1+w)^a} \; dz\; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+a+1}}{w^{m+1}} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \frac{1}{(1+w)^az-w(1+z)^a} \; dz\; dw.$$

This answer being partial we now restrict to $a=2$ and get

$$\frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+3}}{w^{m+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \frac{1}{(z-w)(1-wz)} \; dz\; dw.$$

The pole at $z=w$ is the only one inside the contour and we obtain

$$\frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n+2}}{w^{m+1}} \frac{1}{1-w^2} \; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n+1}}{w^{m+1}} \frac{1}{1-w} \; dw.$$

For the piece $T_{12}$ we follow the same procedure and obtain

$$-\frac{a}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+3}}{w^{m+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-2} \frac{z}{(z-w)(1-wz)} \; dz\; dw$$

which yields

$$-\frac{a}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n+1}}{w^{m}} \frac{1}{1-w^2} \; dw \\ = -\frac{a}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n}}{w^{m}} \frac{1}{1-w} \; dw.$$

Adding the two pieces we obtain for $S_1$

$$\frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n}}{w^{m}} \frac{1}{1-w} \left(\frac{1+w}{w} -2\right) \; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n}}{w^{m}} \frac{1}{1-w} \frac{1-w}{w}\; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n}}{w^{m+1}} \; dw = \frac{1}{n-1} {2m+n\choose m}.$$

Returning to $S_2$ observe that

$${am+1-aq\choose m-q} = \frac{am+1-aq}{m-q} {am-aq\choose m-q-1}$$

so that $${am+1-aq\choose m-q} - a {am-aq\choose m-q-1} = \frac{1}{m-q} {am-aq\choose m-q-1} \\ = \frac{1}{am+1-aq} {am+1-aq\choose q}.$$

Substituting this into $S_2$ yields

$$\sum_{q=0}^m {aq+n-1\choose q} {am+1-aq\choose m-q} - a \sum_{q=0}^m {aq+n-1\choose q} {am-aq\choose m-q-1}.$$

Call these two pieces $T_{21}$ and $T_{22}.$ We recognize piece $T_{21}$ which is the same as piece $T_{11}$ and we obtain

$$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n+1}}{w^{m+1}} \frac{1}{1-w} \; dw.$$

For piece $T_{22}$ we obtain

$$-a \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+2}}{w^{m}} \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \frac{1}{(z-w)(1-wz)} \; dz\; dw.$$

The pole at $z=w$ yields

$$-a \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n+1}}{w^{m}} \frac{1}{1-w^2} \; dw \\ = -a \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n}}{w^{m}} \frac{1}{1-w} \; dw$$

This is the same as piece $T_{12}$ and hence we obtain for $S_2$ when adding $T_{21}$ and $T_{22}$ the contribution

$${2m+n\choose m}$$

for a final answer of $$\left(1+\frac{1}{n-1}\right) {2m+n\choose m} = \frac{n}{n-1} {2m+n\choose m}.$$

Addendum. We can actually solve this for all integer values of $a$ and not only for $a=2.$ Recall the integral for $T_{11}$ where we decided to instantiate $a$ to the value $2:$

$$\frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+a+1}}{w^{m+1}} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \frac{1}{(1+w)^az-w(1+z)^a} \; dz\; dw.$$

Suppose we can prove that $z=w$ is the only pole inside the contour and it is simple. We have

$$\left((1+w)^a z - w(1+z)^a\right)' = (1+w)^a - aw(1+z)^{a-1}.$$

Substituting this into the outer integral yields

$$\frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+a+1}}{w^{m+1}} (1+w)^{n-1} \frac{1}{(1+w)^{a-1}} \frac{1}{1+w-aw}\; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+n+1}}{w^{m+1}} \frac{1}{1+w-aw}\; dw.$$

For the piece $T_{21}$ we get $$-a\frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+a+1}}{w^{m+1}} (1+w)^{n-2} \frac{w}{(1+w)^{a-1}} \frac{1}{1+w-aw}\; dw \\ = -a \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+n}}{w^{m}} \frac{1}{1+w-aw}\; dw.$$

$$\frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+n}}{w^{m}} \left(\frac{1+w}{w} - a\right) \frac{1}{1+w-aw}\; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+n}}{w^{m+1}} (1+w-aw) \frac{1}{1+w-aw}\; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+n}}{w^{m+1}} \; dw = \frac{1}{n-1} {am+n\choose m}.$$

This is precisely the desired result and the pieces $T_{21}$ and $T_{22}$ go through similarly, QED.

• I've added a proof according to OPs comment. Regards, – Markus Scheuer Jan 25 '16 at 0:15

Here is an answer to the second sum that was posted which does indeed use exactly the same method as the first and being more compact is easier to read and understand.

Suppose we seek to verify that

$$\sum_{k=0}^m \frac{q}{pk+q} {pk+q\choose k} {pm-pk\choose m-k} = {mp+q\choose m}.$$

Observe that

$${pk+q\choose k} = \frac{pk+q}{k} {pk+q-1\choose k-1}$$

so that $${pk+q\choose k} - p {pk+q-1\choose k-1} = \frac{q}{k} {pk+q-1\choose k-1} = \frac{q}{pk+q} {pk+q\choose k}.$$

This yields two pieces for the sum, call them $S_1$

$$\sum_{k=0}^m {pk+q\choose k} {pm-pk\choose m-k}$$

and $S_2$

$$- p \sum_{k=0}^m {pk+q-1\choose k-1} {pm-pk\choose m-k}.$$

For $S_1$ introduce the integrals

$${pk+q\choose k} = \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^{pk+q}}{z^{k+1}} \; dz$$

and

$${pm-pk\choose m-k} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm-pk}}{w^{m-k+1}} \; dw.$$

The second one controls the range of the sum because the pole at zero vanishes when $k\gt m$ so we may extend $k$ to infinity, getting for the sum

$$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm}}{w^{m+1}} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^{q}}{z} \sum_{k\ge 0} \frac{w^k}{z^k} \frac{(1+z)^{pk}}{(1+w)^{pk}} \; dz\; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm}}{w^{m+1}} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^{q}}{z} \frac{1}{1-w(1+z)^p/z/(1+w)^p} \; dz\; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm+p}}{w^{m+1}} \frac{1}{2\pi i} \int_{|z|=\gamma} (1+z)^{q} \frac{1}{z(1+w)^p-w(1+z)^p} \; dz\; dw.$$

Suppose $|\epsilon| < |\gamma|$ which makes $\left|\frac{w(1+z)^p}{z(1+w)^p}\right| < 1$ so that we have convergence of the geometric series and suppose we can prove that $z=w$ is the only pole inside the contour and it is simple. We have

$$\left((1+w)^p z - w(1+z)^p\right)' = (1+w)^p - pw(1+z)^{p-1} = (1+w)^{p-1}(1+w-wp).$$

We can choose $|\epsilon|$ small enough such that $|1+w-wp| >0$, so the pole is order 1, which yields

$$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm+p}}{w^{m+1}} (1+w)^q \frac{1}{(1+w)^{p-1}} \frac{1}{1+w-pw} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm+q+1}}{w^{m+1}} \frac{1}{1+w-pw} \; dw.$$

Following exactly the same procedure we obtain for $S_2$

$$-p \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm+q}}{w^{m}} \frac{1}{1+w-pw} \; dw.$$

Adding these two pieces now yields

$$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm+q}}{w^{m}} \left(\frac{1+w}{w} - p\right) \frac{1}{1+w-pw} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm+q}}{w^{m+1}} \; dw \\ = {pm+q\choose m}.$$

Remark Mon Jan 25 2016.

An alternate proof which is completely rigorous and does not depend on assumptions about the poles of a bivariate complex function proceeds from the integral

$$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm}}{w^{m+1}} \sum_{k\ge 0} \frac{w^k}{(1+w)^{pk}} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^{q}}{z^{k+1}} (1+z)^{pk} \; dz\; dw$$

Now put

$$u = \frac{z}{(1+z)^p} \quad\text{and introduce}\quad g(u) = z.$$

We then have $$du = \left(\frac{1}{(1+z)^p} - p\frac{z}{(1+z)^{p+1}}\right) \; dz = \left(\frac{u}{g(u)} - \frac{pu}{1+g(u)}\right) \; dz$$

and $$dz = \frac{1}{u}\frac{g(u) (1+g(u))}{1 + g(u) - p g(u)} \; du.$$

This yields

$$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm}}{w^{m+1}} \sum_{k\ge 0} \frac{w^k}{(1+w)^{pk}} \\ \times \frac{1}{2\pi i} \int_{|u|=\gamma} \frac{1}{g(u) u^{k}} (1+g(u))^q \frac{1}{u}\frac{g(u) (1+g(u))}{1 + g(u) - p g(u)} \; du\; dw$$

or $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm}}{w^{m+1}} \left.(1+g(u))^q \frac{1+g(u)}{1 + g(u) - p g(u)} \right|_{u=w/(1+w)^p} \; dw.$$

Now observe that $g(w/(1+w)^p) = w$ by definition so we get

$$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm}}{w^{m+1}} (1+w)^q \frac{1+w}{1 + w - p w} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm+q+1}}{w^{m+1}} \frac{1}{1 + w - p w} \; dw.$$

This is exactly the same as before and the rest of the proof continues unchanged.

What we have used here is the technique of annihilated coefficient extractors of which there are several more examples at this MSE link I and at this MSE link II and also here at this MSE link III.

Follow the same reasoning when proving this identity, $$\displaystyle \sum_{i=0}^m\frac{q }{pi+q}\binom{pi+q}{i} \binom{pm-pi}{m-i} = \binom{mp+q}{m}$$ You can just read the book yourself. Too difficult to post the book here!

it can be proved using the inversion rule of residue, see page 49 Integral representation and the computation of combinatorial sums