Combination Challenge – 2023/01/06

Proof: Rewrite the left side as: $$\sum_{k=1}^n\binom{n}{k}\binom{n-1}{n-k}$$

The above can be interpreted as the number of ways to choose $n$ balls from $2n-1$ distinct balls, with balls divided into two groups, one group with $k$ distinct balls, the other group with $n-k$ distinct balls.

Therefore the above sum can be re-rewritten as $\boxed{\binom{2n-1}{n}}$.