3
$\begingroup$

Prove that

$\dbinom{n}{k}=\dfrac{n}{n-k}\dbinom{n-1}{k}$

I can come up with a Combinatorial proof for the equivalent identity,

$(n-k) \dbinom{n}{k} = n\dbinom{n-1}{k}$

By selecting a team with a captain from $n$ people in two different ways, but don't know how to do the original one.

Any help will be appreciated.

$\endgroup$
5
$\begingroup$

One way of choosing $k$ people out of $n$ to make a group is done in standard fashion in $\binom nk$ ways.

The other way would be an interesting one :

  • Fix one person called "unspecial". This is done in $n$ ways. He will not be part of our group.

  • From the rest of the $n-1$ people, we choose $k$ people. This is done in $\binom{n-1}k$ ways.

However, note that we are over counting the number of $k$ group people exactly $n-k$ times. To see this, let us say we have to choose $3$ numbers out of $1,2,3,4,5$.

To choose $3,4,5$, we can either declare $1$ "unspecial" and then choose $3,4,5$ out of $2,3,4,5$ , or declare $2$ "unspecial" and then choose $3,4,5$ out of $1,3,4,5$.

Thus, every subset can result from the unspeciality of an element not in that subset. Since the number of possible unspecial elements that will result in the selection of a specific subset of $k$ elements is $n-k$, we see that the answer is also $\frac{n}{n-k}\binom{n-1}{k}$.

Thus, we derive the result.

$\endgroup$
2
$\begingroup$

Here is an inconvenient way to pick $k<n$ numbers out of $[n]=\{1,2,\dots,n\}$. First pick $k$ numbers from $[n-1]$, then decide to do one of the following $1+k$ actions:

  • keep the $k$ numbers in $[n-1]$ you have
  • swap one of the $k$ numbers in $[n-1]$ for $n$

There are $\binom{n-1}{k} (1+k)$ ways you can perform this procedure. If you decided to keep the $k$ original numbers, there is a unique way to obtain the resulting set of $k$ numbers. If you decided to swap, there are $n-k$ ways to obtain the resulting set as there are $n-k$ ways to swap the number $n$ back for one in $[n-1]$. Hence, accounting for over counting, there are $$ \binom{n-1}{k} \left(\frac{1}{1} + \frac{k}{n-k}\right) = \frac{n}{n-k}\binom{n-1}{k} $$ possible results.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.