# Prove the identity ${}_{n}{\rm H}_{n-1}=\sum_{k=0}^{n-1} \left({}_{n-k}{\rm H}_{k} \right)^2$ combinatorially

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.
• I want to show that just definition of ${}_{n}{\rm H}_{k}$: combination with repetition Oct 29, 2019 at 10:15
• @Young You wrote equivalents to the $_nH_k$, and I worked from there. The proof is complete. Oct 29, 2019 at 10:17