# Combinatorial Proof of the following Binomial identity

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.

## 2 Answers

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.

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.