Is there a story proof behind the combinatorial identity $(n-2k)\binom{n}{k} = n\left[ \binom{n-1}{k} - \binom{n-1}{k-1} \right]$?

Question

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?

Answer 1

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.

Answer 2

Brian M. Scott's answer is a nice one for a rearrangement of the identity; here's a perhaps less satisfying argument for the identity as written.

Assume $2k\leq n$ so that $n-2k$ is nonnegative. Let $S = \{1, \ldots, n\}$, and let ${S \choose k}$ denote the set of size-$k$ subsets of $S$, so that $\left\lvert {S \choose k} \right\rvert = {n \choose k}$. Let's suppose (here's the less satisfying part) that we have in hand some bijection $f : {S \choose k} \to {S \choose k}$ such that $t \cap f(t) = \emptyset$ for all $t \in {S \choose k}$. When $n = 2k$ we could just take $f(t) = S - t$, and for general $k \leq n/2$ it can be shown that such a bijection exists, but it seems surprisingly hard to actually construct a natural example of such a bijection when $k < n/2$. (Is there an obvious example I'm missing?)

Assuming we have the bijection, here's an argument for the identity. From our set of $n$ people, we wish to choose a team $t$ of $k$ people, as well as a supervisor that is not in $t \cup f(t)$. (In particular, and in contrast to the "captains" in Brian M. Scott's answer, we view the supervisor as not being a member of the team.)

If we choose the team $t$ first, then there are ${n \choose k}$ ways to choose the team, and, since $t \cap f(t) = \emptyset$, there are exactly $2k$ choices of supervisor that are excluded, so there are $(n - 2k){n \choose k}$ ways to choose both the team and the supervisor.

If we choose the supervisor first, say $v$ is the supervisor, then we have $n$ possible choices for $v$. There are ${n-1 \choose k}$ ways to pick a team $t$ not containing the supervisor, but we also need to enforce the constraint that $v \notin f(t)$. Any team $t$ violating this constraint must have $f(t) = \{v\} \cup q$, where $q$ is a set of $k-1$ people other than $v$. With ${n-1 \choose k-1}$ choices for $q$, and with each choice of $q$ giving exactly one forbidden $t$ since $f$ is a bijection, this gives ${n-1 \choose k} - {n-1 \choose k-1}$ valid choices of team for the given supervisor, so gives $n\left[{n-1 \choose k} - {n-1 \choose k-1}\right]$ ways to assemble the team and supervisor.

Answer 3

Following is a nice combinatorial proof for the identity as written:

Consider a class of $n$ students. You want to reward $k$ number of students, by taking money from the remaining $n-k$ students. What is the money that you will have in the end?

We choose $k$ students to be rewarded in $\dbinom nk$ ways. Money you'll get is $n-k$ dollars, from the remaining students, and the money you'll pay is $k$ dollars. So, you'll have saved $(n-2k)\dbinom nk$ dollars in the end.

This can also be calculated by considering a particular student (to be chosen in $n$ ways). He will pay every time when he is in the non-rewarded set, and he'll be in the non-rewarded set $\dbinom{n-1}k$ number of times, when the rewarded set is chosen by excluding him. He'll get paid every time he is in the rewarded set, and he will be in rewarded set $\dbinom{n-1}{k-1}$ number of times. Therefore, the total money he pays is $\dbinom{n-1}k-\dbinom{n-1}{k-1}$. Multiplying this by $n$ gives the net amount paid by the class, and we are done.