11
$\begingroup$

How can I prove the identity $\sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1}$?

I have to prove it using lattice paths, it should be related to Catalan numbers

The $n$th Catalan number $C_n$ counts the number of monotonic paths along the edges of a grid with $n\times n$ square cells, which do not pass above the diagonal.

See for example this link

For example $\frac{1}{k}\binom{2k-2}{k-1}$ is exactly $C_{k-1}$, and the other terms can also be expressed in terms of the Catalan numbers.

The second part of the exercise ask to prove the recurrence formula $C_n=\sum_{k=1}^n C_{k-1}C_{n-k}$ using similar reasoning (i.e. lattice paths). So we can't use this formula to prove the first.

Could you help me please?

  • 0
    A [related](http://math.stackexchange.com/questions/1559612) question.2015-12-12

2 Answers 2

10

The right-hand side counts the number of monotonic paths from $(0,0)$ to $(n-1,n+1)$. Since $(n-1,n+1)$ is above the diagonal, every one of these paths must cross the diagonal at some point. Suppose that the first ‘bad’ step is from $(k-1,k-1)$ to $(k-1,k)$.

  • How many ways are there to get from $(0,0)$ to $(k-1,k-1)$ without going above the diagonal?

  • How many ways are there to get from $(k-1,k)$ to $(n-1,n+1)$?

3

This one can also be done using complex variables. Suppose we seek to evaluate $\sum_{k=1}^n \frac{1}{k} {2k-2\choose k-1} {2n-2k+1\choose n-k}.$

Introduce the integral representation ${2n-2k+1\choose n-k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n-2k+1}}{z^{n-k+1}} \; dz.$ This has the property that it is zero when $k\gt n.$

We obtain for the sum $\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{n+1}} \sum_{k\ge 1} \frac{1}{k} {2k-2\choose k-1} \frac{z^k}{(1+z)^{2k}} \; dz.$

Recall the generating function for the Catalan numbers $\sum_{q\ge 0} \frac{1}{q+1} {2q\choose q} w^q = \frac{1-\sqrt{1-4w}}{2w}$ This is equal to $\sum_{q\ge 1} \frac{1}{q} {2q-2\choose q-1} w^{q-1}$ so that $\sum_{q\ge 1} \frac{1}{q} {2q-2\choose q-1} w^q = \frac{1-\sqrt{1-4w}}{2}.$

Substitute this into the integral to obtain $\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{n+1}} \frac{1-\sqrt{1-4z/(1+z)^2}}{2} \; dz.$

This has two components, the first is $\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{n+1}} \; dz = \frac{1}{2} {2n+1\choose n}.$

The second is $-\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{n+1}} \sqrt{1-4z/(1+z)^2} \; dz \\ = -\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \sqrt{(1+z)^2-4z} \; dz \\ = -\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \sqrt{(1-z)^2} \; dz \\ = -\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} (1-z) \; dz.$

This evaluates to $\frac{1}{2} {2n\choose n-1} - \frac{1}{2} {2n\choose n}.$

Factoring the sum of the two contributions to reveal the target term we obtain $\frac{1}{2} \left(\frac{2n+1}{n} + 1 - \frac{n+1}{n}\right) {2n\choose n-1} = {2n\choose n-1}.$