[Math] Prove by Combinatorial Argument that $\binom{n}{k}= \frac{n}{k} \binom{n-1}{k-1}$

binomial-coefficientscombinatorial-proofscombinatorics

This is a question from my first proofs homework and I am confused about the combinatorial argument aspect. I already did the algebraic proof. I think I am supposed to put into words what both sides represent? So the LHS would be the number of ways of picking a committee of $k$ members from $n$ people, or number of subsets of size $k$ from a total of $n$, but I don't know how to articulate what is happening on the RHS.

Best Answer

Here's a hint. Try multiplying through by $k$, so it's at least obvious that both sides are integers. Then what you want to show is that $k\binom{n}{k} = n\binom{n-1}{k-1}$. The LHS is now the number of ways to select a committee of $k$ members from $n$ people along with a decision of which of those $k$ will be chairperson. Can you reinterpret this to get the RHS?.

Best Answer

Related Solutions

[Math] Present a combinatorial argument for the identiy $\sum^{n}_{k=1} k\binom{n}{k} = n\cdot 2^{n-1}$

(combinatorial and algebraic) proof that $\sum_{q=1}^n \binom{n}{q}\binom{n-q}{2k-2q}2^{2(k-q)} = \binom{2n}{2k} – \binom{n}{2k}2^{2k}$

Related Question