Using a combinatorial argument, prove that $\displaystyle{\sum_{k=1}^{n} {n \choose k} {n \choose k-1}} = {2n \choose n-1}$

Question

I am aware that similar questions exist on this site but I would like to prove this using Catalan numbers.

---

Using a combinatorial argument, prove that $$\displaystyle{\sum_{k=1}^{n} {n \choose k} {n \choose k-1}} = {2n \choose n-1}$$

---

I think this has to do with Catalan numbers because the right hand side is equal to the number of paths from $(0,0)$ to $(n,n)$ that rise above the line $y=x$ (bad paths). I guessed that the left hand side calculates the number of paths that go above the diagonal at $(k,k)$ for the first time, but I can't see that. How can I prove this?

Answer 1

$$\sum_{k=1}^{n} \binom{n}{k}\binom{n}{k-1}$$ $$=\sum_{k=1}^{n} \binom{n}{n-k}\binom{n}{k-1}$$

Suppose there are $n$ real numbers and $n$ imaginary numbers. And we choose $n-k$ real numbers and $k-1$ imaginary numbers.

Number of ways for this $\binom{n}{k}\binom{n}{k-1}$. So we can choose $n-1$ numbers in $$\sum_{k=1}^{n} \binom{n}{n-k}\binom{n}{k-1}$$ ways

So, in total we choose $n-1$ numbers. That can be done in $\binom{2n}{n-1}$.

This two must be equal.