Proving this identity $\sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1}$ using lattice paths

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?

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)$?

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}.$$