combinatorial identity involving fraction and product of bionomial coefficients

Question

How can I prove the following identity for $i\geq 1$:

$$ \sum_{t=i}^{s-1} \frac{i}{t}\binom{2(s-t-1)}{s-t-1}\binom{2t-i-1}{t-1}= \binom{2s-i-2}{s-1}. $$

Perhaps I'll need to go to hypergeometric functions?

Answer 1

Suppose we seek to verify that

$$\sum_{k=q}^{n-1} \frac{q}{k} {2n-2k-2\choose n-k-1} {2k-q-1\choose k-1} = {2n-q-2\choose n-1}.$$

This is the same as

$$\sum_{k=q}^n \frac{q}{k} {2n-2k\choose n-k} {2k-q-1\choose k-1} = {2n-q\choose n}.$$

which is equivalent to

$$\sum_{k=q}^n \frac{q-k}{k} {2n-2k\choose n-k} {2k-q-1\choose k-1} + \sum_{k=q}^n {2n-2k\choose n-k} {2k-q-1\choose k-1} \\ = {2n-q\choose n}.$$

Now $$\frac{q-k}{k} {2k-q-1\choose k-1} = \frac{q-k}{k} \frac{(2k-q-1)!}{(k-1)! (k-q)!} \\ = - \frac{(2k-q-1)!}{k! (k-q-1)!} = - {2k-q-1\choose k}.$$

It follows that what we have is in fact

$$\sum_{k=q}^n {2n-2k\choose n-k} \left( {2k-q-1\choose k-1} - {2k-q-1\choose k} \right) = {2n-q\choose n}$$

or alternatively

$$\sum_{k=q}^n {2n-2k\choose n-k} \left( {2k-q-1\choose k-q} - {2k-q-1\choose k-q-1} \right) = {2n-q\choose n}.$$

There are two pieces here, call them $A$ and $B$.

We use the integral representation

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

which is zero when $k\gt n$ (pole vanishes) so we may extend $k$ to infinity.

We also use the integral

$${2k-q-1\choose k-q} = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{2k-q-1}}{w^{k-q+1}} \; dw$$

which is zero when $k\lt q$ so we may extend $k$ back to zero.

We obtain for piece $A$

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

The derivation for piece $B$ is the same and yields

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

The difference of these two is

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

Using partial fractions by residues we get

$$\frac{1-w}{(z-w)(z-1/w)} = \frac{1-w}{w-1/w} \frac{1}{z-w} + \frac{1-w}{1/w-w} \frac{1}{z-1/w} \\ = \frac{w(1-w)}{w^2-1} \frac{1}{z-w} + \frac{w(1-w)}{1-w^2} \frac{1}{z-1/w} = - \frac{w}{1+w} \frac{1}{z-w} + \frac{w}{1+w} \frac{1}{z-1/w} \\ = \frac{1}{1+w} \frac{1}{1-z/w} - \frac{w^2}{1+w} \frac{1}{1-wz}.$$

At this point we can see that there will be no contribution from the second term but this needs to be verified. We get for the residue in $z$

$$- \frac{w^2}{1+w} \sum_{p=0}^n {2n+2\choose p} w^{n-p}$$

There is no pole at zero in the outer integral for a contribution of zero.

Continuing with the first term we get

$$\frac{1}{1+w} \sum_{p=0}^n {2n+2\choose p} \frac{1}{w^{n-p}}$$

which yields

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

This is

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

The last integral we will be using is

$${n-p+1\choose n-p-q} = \frac{1}{2\pi i} \int_{|v|=\gamma} \frac{(1+v)^{n-p+1}}{v^{n-p-q+1}} \; dv.$$

Observe that this is zero when $p\ge n$ so we may extend $p$ to infinity, getting

$$\frac{1}{2\pi i} \int_{|v|=\gamma} \frac{(1+v)^{n+1}}{v^{n-q+1}} \sum_{p\ge 0} {2n+2\choose p} (-1)^{n-q-p} \frac{v^p}{(1+v)^{p}} \; dv \\ = (-1)^{n-q} \frac{1}{2\pi i} \int_{|v|=\gamma} \frac{(1+v)^{n+1}}{v^{n-q+1}} \left(1-\frac{v}{1+v}\right)^{2n+2} \; dv \\ = (-1)^{n-q} \frac{1}{2\pi i} \int_{|v|=\gamma} \frac{1}{v^{n-q+1}} \frac{1}{(1+v)^{n+1}} \; dv \\= (-1)^{n-q} (-1)^{n-q} {n-q+n\choose n} = {2n-q\choose n}.$$

This is the claim. QED.