Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}$

Question

Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}$

I have expanded it this far:

$$\frac{k \cdot n!}{k!(n-k)!} = \frac{n \cdot (n-1)!}{(k-1)!(n-k)!} $$

but then I am stuck from where to go from there.

Answer 1

To select a committee of $k$ people with a president from a group of $n$ people, you can

1. select the $k$ committee members, and then select the president from the members, or
2. select the president from the $n$ people, and the $k-1$ remaining committee members from the remaining $n-1$ people.

Answer 2

Here is a more comprehensive combinatorial proof.

Given $n$ people, we can form a committee of size $k$ in ${n\choose k}$ ways. Once the committee is formed we can pick a committee leader in $k$ ways. Thus we can form a committee of size $k$ with a committee leader in $k{n\choose k}$ ways. We can count the same thing by first picking a committee leader in $n$ ways. Once this has been done we can form the committee with the remaining $n-1$ people in ${n-1\choose k-1}$ ways. We choose $k-1$ people from $n-1$ people because a leader has already been specified. Thus we can pick a committee leader first and then form the committee with the remaining people in $n{n-1\choose k-1}$ ways. Hence $k{n\choose k}=n{n-1\choose k-1}$.

Answer 3

Left Side = $k\binom{n}{k} = k\frac{n!}{k!(n-k)!}$

Because $\frac{k}{k!} = \frac{1}{(k-1)!}$

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

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

Because $n(n-1)! = n!$

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

Left Side = Right side, therefore proved !!