<s>[INST] 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?
 [/INST] 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}.$$
</s>