Using a combinatorial proof , prove that if n and k are integers with $1\le k \le n$, then $ n\binom {n-1}{k-1} = k \binom nk $

Question

How should I solve this problem? can anyone help?

Thanks.

Answer 1

The expression on the left can been seen as choosing a committee of $k$ members out of $n$ people and then choosing a "president" from within the committee.

Meanwhile, the expression on the right can be seen as first choosing a president out of $n$ people before choosing the rest ($k-1$ members) of the committee from the remaining $n-1$ people.

Both count the same scenario so they are equal. (Remark: this is similar to the hint, changing the words "committee" and "president" to "subsets" and "elements" to use the hint given).

Answer 2

We show that each side of the equation counts the number of ways to choose from a set with $n$ elements, a subset with $k$ elements and a distinguished element of that set. Further, on the left hand side, we first choose the $k$ element set which can be done in $\binom{n}{k}$ ways. Also, we choose one of the $k$ elements in this subset to be the distinguished element out of the entire $n$ element set which is done in $n$ ways. Choose the remaining $k-1$ elements of the subset from the remaining $n-1$ elements of the subset which is done in $\binom{n-1}{k-1}$ ways. So we have one direction.

As for the other direction, when $1\leq k \leq n$ and $n,k \in \mathbb{Z}$, then

$k\binom{n}{k} = k\frac{n!}{(n-k)!k!}=\frac{n(n-1)!}{(n-1+1-k)!(k-1)!}=n\frac{(n-1)!}{((n-1)-(k-1))!(k-1)!}=n\binom{n-1}{k-1}.$