Story proof for choosing committee with pre-designated president

Question

The problem is to come up with story proof for the following:

Show that for all positive integers n and k with n $\geq$ k, $$\mathbf{\binom{n}{k}+ \binom{n}{k-1} = \binom{n+1}{k}},$$ doing this with a story, giving an interpretation for why both sides count the same thing. Hint for the story proof: Imagine n + 1 people, with one of them pre-designated as “president”.

The explanation I found is following:

Suppose from a group of $\mathbf{n+1}$ people we have to form a committee comprising of $\mathbf{k}$ people. Also in this group one person is pre-designated as president. The number of ways of forming this committee is given by $\mathbf{\binom{n+1}{k}}$ which is the right-hand side of the identity. We can also think of forming the committee in two ways, one in which the president $\mathbf{is}$ chosen and out of the remaining $\mathbf{n}$ people we choose $\mathbf{k-1}$ and one in which the president is $\mathbf{not}$ chosen and we choose $\mathbf{k}$ people from $\mathbf{n}$ people. Summing these two cases we get $\mathbf{\binom{n}{k-1} + \binom{n}{k}}$ which is the left-hand side of the identity.

I have no questions regarding the second term "n choose k" — the (n+1)th person that was left out is the pre-designated as president. However the first term baffles me. If the (n+1)th person isn't a president than how the term can account for all group, and how the committee is guaranteed to include the pre-designated president.

I know that I probably don't understand something obvious and would be grateful if someone could point me in the right direction.

Answer 1

For me the translation of "choosing form $n+1$ a committee of $k$ people of which $1$ is president" would lead to the identity $${n+1 \choose k}{k \choose 1} = {n+1 \choose 1}{n \choose k-1}$$

For the identity you are showing, you can either select the committee from the first $n$ people so ${n\choose k}$ ways, or choose $k-1$ from the first $n$ and then also choose the $n+1^{\text{th}}$ person so ${n\choose k-1}$ times $1$, but these need to sum to the more natural ${n+1\choose k}$, leading to $${n\choose k}+{n\choose k-1}={n+1\choose k}$$ but this does not involve predesignating somebody as president

Answer 2

I'm not sure I understand your question, but I think you are not understanding how the $\binom{n}{k-1}$ is formed.

---

Assume that the $(n-1)^{\text{th}}$ person is the president. We already counted the case when the president isn't in the $k$ chosen people in $\binom{n}{k}$, so in this case the president IS in the $k$-person committee. We have $(n+1)-1 = n$ people left to choose from after we have included the president in the committee, and we need $k-1$ more people in our committee as we have already chosen $1$ (the president) to be one of the $k$ people. Thus, in this part where the president IS included in the $k$-person committee gives $\boxed{\binom{n}{k-1}}$