Combinatorial Proof ${n \choose k}\cdot (n-k)\cdot 2^{k} = \sum_{i=1}^{k+1} {n\choose i}\cdot{n-i\choose k-i+1}\cdot i $

Question

I need to prove: $${n \choose k}\cdot (n-k)\cdot 2^{k} = \sum_{i=1}^{k+1} {n\choose i}\cdot{n-i\choose k-i+1}\cdot i $$ I will be very grateful if anyone can help, I really have no idea how to prove it. Thanks :)

Answer 1

Tinkle around with the summand \begin{eqnarray*} i \binom{n}{i} \binom{n-i}{k-i-1} &=& \frac{n!}{\color{blue}{(n-i)!}(i-1)!} \frac{ \color{blue}{(n-i)!}}{(k-i+1)!(n-k-1)!} \\ &=& \frac{\color{red}{k!}}{(i-1)!k-i+1)! } (n-k) \frac{ n!}{\color{red}{k!}(n-k)!} \\ &=& (n-k) \binom{ n}{k} \binom{k}{i-1}. \\ \end{eqnarray*} So ... \begin{eqnarray*} \sum_{i=1}^{k+1} i \binom{n}{i} \binom{n-i}{k-i-1} &=& (n-k) \binom{ n}{k}\sum_{j=0}^{k} \binom{k}{j} =\cdots\\ \end{eqnarray*}

Answer 2

Break it down into words.

The LHS you are taking the product of choosing $k$ items from an $n$-element set, then choosing a subset of the $k$-element set you create, then choosing one item from the remaining $n−k$ elements.

The RHS, you are choosing $i$ elements from an $n$-element set, then choosing $k−i+1$ items from a set with $n−i$ elements, then choosing one of the $i$ elements, for each $i=1$ to $i=k+1$. So, the RHS, you wind up with a set of size $i$ and a set of size $k−i+1$. Together, this is a set of size $k+1$, and you choose one of the $i$-items. Do you see the bijection?

Answer 3

I too am new to combinatorial proofs, and perhaps my naive story-telling approach to solving the problem may help newer, less familiar people with the concept gain some intuition.

Suppose we have n people at the police station, and we know that k are criminals. There are $n \choose k$ ways to select such a group. Suppose further, that a subset of these is guilty of not any crime, but robbing the world bank. From the initial pool of criminals, we have $2^k$ ways to choose such a group.

In a plot twist, one of the people we thought was innocent turned out to be the ring-leader of the robbery. There are $n-k$ innocents, and hence $n-k$ ways to choose the ringleader. He is added to the selected subset, and we have a group of $k+1$ people, guilty ringleader included, who robbed the bank.

It is clear to see that the ways of performing this is the product ${n \choose k} \times 2^k \times (n-k)$ ways to first selected the criminals, then select the group to rob the bank, then to choose one of the initial innocents to turn out to be the ringleader. Note that different k size groups of selected criminals may yield the same subset of bank robbers, so we cannot eliminate the first factor from our scenario.

Now what about the second one? Since we see the $2^k$ in the first one, we can guess the second one will be summing sets of size k or something of that sort.

We observe that i ranges from 1 to $k+1$, and we have the term $n \choose i$. This means we are iterating over a subset sized 1 to $k+1$. Then, we notice the multiplication by $i$. Neglect the other term for now; this is exactly the way to choose k+1 bank robbers, among whom we select 1 leader!

We are not done yet. Remember, we have one term left, and we still didn't choose who else in the room are criminals (in the first case there are k criminals total, and here we will get that too. Simply put, if we have a subset sized i of bank robbers, one of whom is a leader and was chosen from the innocent pool, so i-1 robbers from the initial pool of criminals, then we must have from the n-i people who did not rob the bank, $k-(i-1)$ who are just regular criminals and not bank robbers. And there are $n-i \choose k-i+1$ ways to do this. In summary, we are iterating from $1$ to $k+1$, choosing a group of robbers and their leader, and then selecting from the remaining people a necessary number to form the full set of criminals, robbers and not robbers. (Excluding the leader). $$\sum_{i=1}^{k+1} \binom{n}{i}\times i\times \binom{n-i}{k-i-1}$$

Only then does the second scenario become identical to the first, and all the ways possible in the 2nd way are possible in the first. Even though we changed the order in the 2nd way, first choosing the bank robbers, and then choosing ordinary criminals, rather than choosing all criminals then designating robbers among them, it remains the same.

I hope this servers as a pathway to whomever needs some help with combinatorial/bjiective proofs.