I would appreciate if somebody could help me with the following problem:
Prove the identity $${}_{n}{\rm H}_{n-1}=\sum_{k=0}^{n-1} \left({}_{n-k}{\rm H}_{k} \right)^2 $$ (for $n$ a positive integer) combinatorially. (${}_{n}{\rm H}_{k}=\binom{n+k-1}{k}$)
I've tried transforming it into $$\left({}_{n-k}{\rm H}_{k} \right)^2 = \left(\binom{n-1}{k} \right)^2=\binom{n-1}{k}\binom{n-1}{n-1-k}$$ then $$\sum_{k=0}^{n-1} \left({}_{n-k}{\rm H}_{k} \right)^2 =\binom{2n-2}{n-1}$$ I want show!! combinatorially
Say you have $2(n-1)$ distinct objects. How many ways are there to select $n-1$ of them? That number is $\binom{2(n-1)}{n-1}$, the LHS. But you can also divide the objects into two sets of $n-1$, then select $k$ from the first set and $n-1-k$ from the second set, where $0\le k\le n-1$. That is, $\sum_{k=0}^{n-1}\binom{n-1}k\binom{n-1}{n-1-k}$ ways – the RHS.