1
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I want to show that just definition of ${}_{n}{\rm H}_{k}$: combination with repetition $\endgroup$
    – Young
    Oct 29, 2019 at 10:15
  • $\begingroup$ @Young You wrote equivalents to the $_nH_k$, and I worked from there. The proof is complete. $\endgroup$ Oct 29, 2019 at 10:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .