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.
On
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:
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.
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.