# 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]$?

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?

• You mean proof by something like real-world "choosing" interpretation? Commented Jul 17, 2020 at 18:34
• Yeah, like from a set of n elements first choose k elements and then choose an element from the k chosen elements.... Commented Jul 17, 2020 at 18:38
• This is sometimes referred to as a "combinatorial proof" Commented Jul 17, 2020 at 18:39
• Can you think of combinatorial proofs for the two identities? If so you might be able to sew them together into a miniseries proof of the main one Commented Jul 17, 2020 at 18:41

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.

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.

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.