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