Is there a "story proof"/combinatorial proof for the following combinatorial identity:
$$(n-2k)\binom{n}{k} = n\left[ \binom{n-1}{k} – \binom{n-1}{k-1} \right]\tag1$$
I know that this identity can be proved by using the following identities:
$$k\binom{n-1}{k} = (n-k)\binom{n-1}{k-1}\tag2$$
$$k\binom{n}{k} = n\binom{n-1}{k-1}\tag3$$
but is there a "story proof" for equation $(1)$?
Edit 1: I do know the story proofs for equations 2 and 3. But 'sewing them together' is the problem!
$$\text{RHS} \stackrel{\text{i}}{=} n\left[ \binom{n-1}{k} – \binom{n-1}{k-1} \right] \stackrel{\text{ii}}{=} \frac{n}{k}\left[ k\binom{n-1}{k} – k\binom{n-1}{k-1} \right] \stackrel{\text{iii}}{=} \frac{n}{k}\left[ (n-k)\binom{n-1}{k-1} – k\binom{n-1}{k-1} \right] \stackrel{\text{iv}}{=} \frac{n}{k}\binom{n-1}{k-1}\left[ (n-k) – k \right] \stackrel{\text{v}}{=} (n-2k)\binom{n}{k}$$
Precisely, how do you formulate a story proof for step (iv)? i mean the term $\binom{n-1}{k-1}$ is being taken common in step iv. What could a story proof for taking a term common be?
Best Answer
I can come up with a combinatorial argument if I rearrange the identity a little. We’re starting with
$$(n-2k)\binom{n}k=n\left[\binom{n-1}k-\binom{n-1}{k-1}\right]\;,$$
which is clearly the same as
$$(n-k)\binom{n}{n-k}-k\binom{n}k=n\binom{n-1}k-n\binom{n-1}{k-1}\;.$$
Transposing the two negative terms yields
$$(n-k)\binom{n}{n-k}+n\binom{n-1}{k-1}=n\binom{n-1}k+k\binom{n}k\;.\tag{1}$$
Now suppose that we have a group of $n$ athletes, and we want to form a team of either $k$ or $n-k$ players and choose one member of the team to be its captain; in how many different ways can we do this?
We can choose a team of $n-k$ in $\binom{n}{n-k}$ ways; having done that, we can choose its captain in $n-k$ ways, so there are $(n-k)\binom{n}{n-k}$ ways to choose this team and its captain. To form a team of $k$ players we can first choose one of the $n$ athletes to be its captain, after which there are $\binom{n-1}{k-1}$ ways to choose the other $k-1$ players from the remaining $n-1$ athletes, so there are altogether $n\binom{n-1}{k-1}$ ways to choose this team and its captain. Thus, the lefthand side of $(1)$ is the number of ways to choose a team of $k$ or $n-k$ players and appoint its captain.
Alternatively, we can choose a team of $k$ players in $\binom{n}k$ ways, after which we can select its captain in $k$ ways, so there are $k\binom{n}k$ ways to choose a team of $k$ and its captain. To form a team of $n-k$ players, we can first choose any one of the $n$ athletes to be its captain. Then to fill out the rest of the team we can choose the $k$ the remaining $n-1$ athletes who will not be on the team in $\binom{n-1}k$ ways. Thus, there are $n\binom{n-1}k$ ways to form a team of $n-k$ and choose its captain, and the righthand side of $(1)$ is also the number of ways to choose a team of $k$ or $n-k$ players and appoint its captain.