BasicCombinatorialIdentity Basic

Problem - 2681

Show that $$\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$$


Solution 1: Apply the definition

Applying the basic definition on the right side: $$\frac{n}{k}\times \binom{n-1}{k-1}=\frac{n}{k}\times\frac{(n-1)!}{(k-1)!(n-k)!}=\frac{n!}{k!(n-k)!}=\binom{n}{k}$$

Solution 2: The Multi-Approach Method

Let's consider this question: how many ways to select $k$ people of out $n$ candidates to form a team and also designate one team captain?

If we first choose $k$ people, there are ${n\choose k}$ ways, then from these people there are $k$ choice to designate a captain. Hence, totally, there are $k{n\choose k}$ ways.

Alternatively, we can first pick one from the $n$ people to be the captain. There are $n$ ways. The next step is to pickup $(k-1)$ team members from the remaining $(n-1)$ candidates. There are ${n-1 \choose k-1}$ ways. Accordingly, the answer is $n{n-1\choose k-1}$.

Because they are just two different approaches to solve the same proble, therefore the answer must be the same: $$k{n\choose k}=n{n-1 \choose k-1} \implies {n\choose k}=\frac{n}{k}{n-1 \choose k-1}$$

 

report an error