How can I prove this combinatorial identity $\sum_{j=0}^n j\binom{2n}{n+j}\binom{m+j-1}{2m-1}=m\cdot4^{n-m}\cdot\binom{n}{m}$?

Question

Let $n,m$ be non-negative integers.

How can one prove the following identity?

$$\sum_{j=0}^n j\binom{2n}{n+j}\binom{m+j-1}{2m-1}=m\cdot4^{n-m}\cdot\binom{n}{m}$$

Answer 1

Let :

$$f_n:=\sum_{j=0}^n j\binom{2n}{n+j}\binom{m+j-1}{2m-1}$$

$$g_n:=m\cdot4^{n-m}\cdot\binom{n}{m}$$

I will do the "snake-oil method" (it is hardcore I must admit, have fun...) as seen in the following (wonderful) reference :

http://www.math.upenn.edu/~wilf/DownldGF.html

The idea, instead of showing $f_n=g_n$ for all $n$, take the associated formal power series $F$ and $G$ and show $F=G$, the snake oil method applies because $f_n$ is defined with a sum (I will invert the two sums and I will get the solution).

Then set :

$$ F(X):=\sum_{n=0}^{+\infty}f_nX^n\text{ and }G(X):=\sum_{n=0}^{+\infty}g_nX^n$$

You have :

$$G(X)=\sum_{n=0}^{+\infty}m\cdot4^{n-m}\cdot\binom{n}{m}X^n=\sum_{n=m}^{+\infty}m\cdot4^{n-m}\cdot\binom{n}{m}X^{n} $$

Then :

$$G(X)=\sum_{n=0}^{+\infty}m\cdot4^{n}\cdot\binom{n+m}{m}X^{n+m}=mX^m\sum_{n=0}^{+\infty}\binom{n+m}{m}(4X)^n=m\frac{X^m}{(1-4X)^{m+1}} $$

On the other hand :

$$F(X)=\sum_{n=0}^{+\infty}\sum_{j=0}^n j\binom{2n}{n+j}\binom{m+j-1}{2m-1}X^n=\sum_{j=0}^{+\infty}\sum_{n=j}^{+\infty} j\binom{2n}{n+j}\binom{m+j-1}{2m-1}X^n $$

$$F(X)=\sum_{j=0}^{+\infty}j\binom{m+j-1}{2m-1}\sum_{n=j}^{+\infty} \binom{2n}{n+j}X^n=\sum_{j=0}^{+\infty}j\binom{m+j-1}{2m-1}X^j\sum_{n=0}^{+\infty} \binom{2n+2j}{n+2j}X^n $$

And use the identity page 54 of the reference I have given to get :

$$\sum_{n=0}^{+\infty} \binom{2n+2j}{n}X^n=\frac{1}{\sqrt{1-4X}}(\frac{1-\sqrt{1-4X}}{2X})^{2j}$$

$$F(X)=\sum_{j=0}^{+\infty}j\binom{m+j-1}{2m-1}X^j\frac{1}{\sqrt{1-4X}}(\frac{1-\sqrt{1-4X}}{2X})^{2j}$$

Set $Y:=\sqrt{1-4X}$ then :

$$F(X)=\sum_{j=0}^{+\infty}j\binom{m+j-1}{2m-1}\frac{1}{(4X)^j}\frac{1}{Y}(1-Y)^{2j}$$

But $4X=1-Y^2$ so :

$$F(X)=\sum_{j=0}^{+\infty}j\binom{m+j-1}{2m-1}\frac{1}{(1-Y^2)^j}\frac{1}{Y}(1-Y)^{2j}$$

And then it reduces :

$$\frac{(1-Y)^{2j}}{(1-Y^2)^j} =\frac{(1-Y)^j}{(1+Y)^j}$$

$$F(X)=\frac{1}{Y}\sum_{j=0}^{+\infty}j\binom{m+j-1}{2m-1}Z^j\text{ where } Z:=\frac{1-Y}{1+Y}$$

This looks like a usual formal power series now :

$$F(X)=\frac{1}{Y}\sum_{j=m}^{+\infty}j\binom{m+j-1}{2m-1}Z^j=\frac{Z^m}{Y}\sum_{j=0}^{+\infty}(j+m)\binom{2m+j-1}{2m-1}Z^j$$

$$F(X)=\frac{Z^m}{Y}\sum_{j=0}^{+\infty}(j+m)\binom{2m+j-1}{j}Z^j$$

Now

$$\sum_j \binom{2m+j-1}{j}Z^j=\frac{1}{(1-Z)^{2m}}$$

And

$$\sum_j j\binom{2m+j-1}{j}Z^j=ZD(\frac{1}{(1-Z)^{2m}})=\frac{2mZ}{(1-Z)^{2m+1}} $$

Hence :

$$F(X)=\frac{Z^m}{Y}(\frac{m}{(1-Z)^{2m}}+\frac{2mZ}{(1-Z)^{2m+1}})=\frac{1}{Y}(\frac{Z}{(1-Z)^2})^mm\frac{1+Z}{1-Z} $$

By an easy calculation :

$$\frac{Z}{(1-Z)^2}=\frac{X}{Y^2}\text{ and } \frac{1+Z}{1-Z}=\frac{1}{Y}$$

$$F(X)=\frac{X^mm}{(Y^2)^{m+1}}=G(X)$$

Formal power series are equal, hence the coefficients must be. I don't know if there exists a "better" answer to this.

Answer 2

Suppose we seek to verify that $$\sum_{q=0}^n q {2n\choose n+q} {m+q-1\choose 2m-1} = m \times 4^{n-m} \times {n\choose m}$$ where $n\ge m.$

We use the integrals $${2n\choose n+q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-q+1}} \frac{1}{(1-z)^{n+q+1}} \; dz.$$

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

Observe that the first integral is zero when $q\gt n$ so we may extend $q$ to infinity.

This yields for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{(1-z)^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{m-1}}{w^{2m}} \sum_{q\ge 0} q \frac{z^q (1+w)^q}{(1-z)^q} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{(1-z)^{n+1}} \\ \times \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{m-1}}{w^{2m}} \frac{z(1+w)/(1-z)}{(1-z(1+w)/(1-z))^2} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{(1-z)^{n+1}} \\ \times \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{m-1}}{w^{2m}} \frac{z(1+w)(1-z)}{(1-z-z(1+w))^2} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n}} \frac{1}{(1-z)^{n}} \\ \times \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{m}}{w^{2m}} \frac{1}{(1-2z-zw)^2} \; dw \; dz.$$

We evaluate the inner integral using the negative of the residue at the pole at $w=(1-2z)/z,$ starting from $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+2}} \frac{1}{(1-z)^{n}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{m}}{w^{2m}} \frac{1}{(w-(1-2z)/z)^2} \; dw \; dz.$$

Differentiating we have $$m\frac{(1+w)^{m-1}}{w^{2m}} - 2m \frac{(1+w)^m}{w^{2m+1}} = \left(w-2(1+w)\right) m\frac{(1+w)^{m-1}}{w^{2m+1}} \\ = (-w-2) m\frac{(1+w)^{m-1}}{w^{2m+1}}.$$

The negative of this evaluated at $w=(1-2z)/z$ is $$\frac{1}{z} \times m \times \frac{(1-z)^{m-1}}{z^{m-1}} \times \frac{z^{2m+1}}{(1-2z)^{2m+1}}$$

which finally yields $$\frac{m}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-m+1}} \frac{1}{(1-z)^{n-m+1}} \frac{1}{(1-2z)^{2m+1}} \; dz.$$

We have that the residues at zero, one and one half sum to zero with the first one being the sum we are trying to compute. Therefore we evaluate these in turn. We will restore the front factor of $m$ at the end.

For the residue at zero we have using the Cauchy product that $$\sum_{q=0}^{n-m} {n-m+q\choose q} 2^{n-m-q} {2m+n-m-q\choose n-m-q} \\ = \sum_{q=0}^{n-m} {n-m+q\choose q} 2^{n-m-q} {m+n-q\choose 2m}.$$

For the residue at one we have that $$\frac{(-1)^{n-m+1}}{(n-m)!} \left(\frac{1}{z^{n-m+1}} \frac{1}{(1-2z)^{2m+1}}\right)^{(n-m)} \\= \frac{(-1)^{n-m+1}}{(n-m)!} \sum_{q=0}^{n-m} {n-m\choose q} (-1)^q \frac{(n-m+q)!}{(n-m)!\times z^{n-m+1+q}} \\ \times 2^{n-m-q} \frac{(2m+n-m-q)!}{(2m)!\times (1-2z)^{2m+1+n-m-q}} \\= \frac{(-1)^{n-m+1} 2^{n-m}}{(n-m)!} \sum_{q=0}^{n-m} {n-m\choose q} (-1)^q \frac{(n-m+q)!}{(n-m)!\times z^{n-m+1+q}} \\ \times 2^{-q} \frac{(m+n-q)!}{(2m)!\times (1-2z)^{m+1+n-q}}.$$

Evaluate this at one to get $$2^{n-m} \sum_{q=0}^{n-m} {n-m+q\choose q} 2^{-q} {m+n-q\choose 2m}.$$

The residue at one evaluates to the sum we seek just like the residue at zero. This leaves the residue at one half, where we find $$\frac{(-1)^{2m+1}}{(2m)!\times 2^{2m+1}} \left(\frac{1}{z^{n-m+1}} \frac{1}{(1-z)^{n-m+1}}\right)^{(2m)} \\ = \frac{(-1)^{2m+1}}{(2m)!\times 2^{2m+1}} \sum_{q=0}^{2m} {2m\choose q} (-1)^q \frac{(n-m+q)!}{(n-m)!\times z^{n-m+1+q}} \\ \times \frac{(n-m+2m-q)!}{(n-m)! \times (1-z)^{n-m+1+2m-q}} \\ = \frac{(-1)^{2m+1}}{(2m)!\times 2^{2m+1}} \sum_{q=0}^{2m} {2m\choose q} (-1)^q \frac{(n-m+q)!}{(n-m)!\times z^{n-m+1+q}} \\ \times \frac{(n+m-q)!}{(n-m)! \times (1-z)^{n+m+1-q}}.$$

Evaluate this at one half to get $$-\frac{1}{2^{2m+1}} \sum_{q=0}^{2m} {n-m+q\choose q} (-1)^q 2^{n-m+1+q} {n+m-q\choose 2m-q} 2^{n+m+1-q} \\ = - 2^{2n-2m+1} \sum_{q=0}^{2m} {n-m+q\choose q} (-1)^q {n+m-q\choose 2m-q}.$$

For this last sum use the integral $${n+m-q\choose 2m-q} = {n+m-q\choose n-m} = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{2m-q+1}} \frac{1}{(1-v)^{n-m+1}} \; dv.$$

This controls the range so we can let $q$ go to infinity in the sum to get $$\frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{2m+1}} \frac{1}{(1-v)^{n-m+1}} \sum_{q\ge 0} {n-m+q\choose q} (-1)^q v^q \; dv \\ = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{2m+1}} \frac{1}{(1-v)^{n-m+1}} \frac{1}{(1+v)^{n-m+1}} \; dv \\ = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{2m+1}} \frac{1}{(1-v^2)^{n-m+1}} \; dv = {n-m+m\choose m} = {n\choose m}.$$

We have shown that $$2S - m\times 2\times 2^{2n-2m} \times {n\choose m} = 0$$ and hence may conclude that $$S = m \times 4^{n-m} \times {n\choose m}.$$

Remark. If we want to do this properly we also need to verify that the residue at infinity of the integral in $w$ is zero. Recall the formula for the residue at infinity

$$\mathrm{Res}_{z=\infty} h(z) = \mathrm{Res}_{z=0} \left[-\frac{1}{z^2} h\left(\frac{1}{z}\right)\right]$$

In the present case this becomes

$$-\mathrm{Res}_{w=0} \frac{1}{w^2} \frac{(1+1/w)^m}{1/w^{2m}} \frac{1}{(1-2z-z/w)^2} \\ = -\mathrm{Res}_{w=0} \frac{(1+1/w)^m}{1/w^{2m}} \frac{1}{(w(1-2z)-z)^2} \\ = -\mathrm{Res}_{w=0} (1+w)^m w^m \frac{1}{(w(1-2z)-z)^2}$$ which is zero by inspection.

The same procedure applied to the main integral yields

$$-\mathrm{Res}_{z=0} \frac{1}{z^2} z^{n-m+1} \frac{1}{(1-1/z)^{n-m+1}} \frac{1}{(1-2/z)^{2m+1}} \\ = -\mathrm{Res}_{z=0} \frac{1}{z^2} z^{n-m+1} \frac{z^{n-m+1}}{(z-1)^{n-m+1}} \frac{z^{2m+1}}{(z-2)^{2m+1}} \\ = -\mathrm{Res}_{z=0} z^{2n+1} \frac{1}{(z-1)^{n-m+1}} \frac{1}{(z-2)^{2m+1}}$$ which is zero as well.

Answer 3

Remark. This is my attempt to streamline the first proof. Not quite as simple as I had hoped but a start.

Suppose we seek to verify that $$S = \sum_{q=0}^n q {2n\choose n+q} {m+q-1\choose 2m-1} = m \times 4^{n-m} \times {n\choose m}$$ where $n\ge m.$

This is

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

which has two pieces. We use the integral

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

Observe that this integral vanishes when $q\gt n-m$ and we may extend $q$ to $2n$. We get for the first piece

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

The second piece is the negative of

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

This vanishes through its integral representation when $q\gt n-m-1$ and we obtain

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

Joining the two pieces we arrive at the single integral

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

We know the residues at zero, minus one and infinity sum to zero, where the first represents the queried sum. For the residue at minus one it is given by

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

We see that this residue also represents the queried sum. This leaves the residue at infinity which is

$$\mathrm{Res}_{w=\infty} \frac{1}{w^{n-m+1}} \frac{1}{(1+w)^{n+1-m}} (1+2w)^{2n-1} \\ = - \mathrm{Res}_{w=0} \frac{1}{w^2} w^{n-m+1} \frac{1}{(1+1/w)^{n+1-m}} (1+2/w)^{2n-1} \\ = - \mathrm{Res}_{w=0} w^{n-m-1} \frac{w^{n+1-m}}{(1+w)^{n+1-m}} \frac{(2+w)^{2n-1}}{w^{2n-1}} \\ = - \mathrm{Res}_{w=0} \frac{1}{w^{2m-1}} \frac{(2+w)^{2n-1}}{(1+w)^{n+1-m}}.$$

Extracting coefficients we find

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

Introduce (this vanishes when $q\gt 2m-2$)

$${2n-1\choose 2m-2-q} = {2n-1\choose 2n+1-2m+q} \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2m-1-q}} \frac{1}{(1-z)^{2n-2m+2+q}} \; dz$$

to get for the sum

$$-\frac{n 2^{2n-2m+1}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2m-1}} \frac{1}{(1-z)^{2n-2m+2}} \sum_{q\ge 0} {n-m+q\choose q} 2^q (-1)^q \frac{z^q}{(1-z)^q} \; dz \\ = -\frac{n 2^{2n-2m+1}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2m-1}} \frac{1}{(1-z)^{2n-2m+2}} \frac{1}{(1+2z/(1-z))^{n-m+1}} \; dz \\ = -\frac{n 2^{2n-2m+1}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2m-1}} \frac{1}{(1-z)^{n-m+1}} \frac{1}{(1+z)^{n-m+1}} \; dz \\ = -\frac{n 2^{2n-2m+1}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2m-1}} \frac{1}{(1-z^2)^{n-m+1}} \; dz \\ = -n 2^{2n-2m+1} [z^{2m-2}] \frac{1}{(1-z^2)^{n-m+1}} = -n 2^{2n-2m+1} [z^{m-1}] \frac{1}{(1-z)^{n-m+1}} \\ = -n 2^{2n-2m+1} {n-m+m-1\choose m-1}.$$

It follows that

$$2S -n 2^{2n-2m+1} {n-1\choose m-1} = 0 \quad\text{or}\quad S = n 4^{n-m} \frac{m}{n} {n\choose m}$$

which yields

$$\bbox[5px,border:2px solid #00A000]{ S = m \times 4^{n-m} \times {n\choose m}.}$$

as claimed.