Category Archives: Combinatorics

Prove $$\sum_{k=1}^n\binom{n}{k}\binom{n-1}{k-1}=\binom{2n-1}{n}$$ 🔑 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, … Continue reading →