Combinatorial proof of $\binom{n+1}{k}=\frac{(n+1)\binom{n}{k-1}}{k}$

Question

I don't know how to prove this using combinatorial proof. $$\binom{n+1}{k}=\frac{(n+1)\binom{n}{k-1}}{k}$$

I know $\binom{n+1}{k}$ means choose $k$ elements from a set with $n+1$ elements, and $\binom{n}{k-1}$ means select $k-1$ elements from one of it subset with $n$ elements. (There are $n+1$ subsets with $n$ elements in a set with $n+1$ elements.) But I don't know how to deal with $\frac{1}{k}$.

Answer 1

Easier to think of it as $k\binom{n+1}{k}=(n+1)\binom{n}{k-1}$. Suppose there are $n+1$ students in my class, I want to choose a group of $k$ students and I want to choose one of them to be the leader of the group. One way to do this is to choose a group of $k$ students ($\binom{n+1}{k}$ options) and then from this group there are $k$ options to choose the leader. So there are $k\binom{n+1}{k}$ options for me. Another way would be first to choose the leader of the group ($n+1$ options to do that) and then from the remaining $n$ students I need to choose $k-1$ more for the group. So there are $(n+1)\binom{n}{k-1}$ options.

Answer 2

Say you have $n+1$ people, and you need to choose a committee of $k$ people with a leader. You can choose the $k$ people and then pick the leader from them in $k\binom{n+1}k$ ways. Alternatively, you can choose the leader first in $n+1$ ways and then fill out the rest of the committee in $n\choose{k-1}$ ways. Hence, $$k\binom{n+1}k=(n+1)\binom n{k-1}$$.

Answer 3

Here's a combinatorial proof that ${n+1\choose k}k=(n+1){n\choose k-1}$: Starting with $n+1$ people, you can form a committee of $k$ people in $n+1\choose k$ ways, and then pick a chair for the committee among them in $k$ ways, or you can start by picking a chair in $n+1$ ways and then select the remaining committee members in $n\choose k-1$ ways.

Answer 4

First choose one of $n+1$ elements.

Then choose $k-1$ of the remaining $n$ elements.

This gives at first glance $(n+1)\binom{n}{k-1}$ possibilities to choose $k$ out of $n+1$ elements.

However, now realize that every $k$-tuple $(a_1,\dots,a_k)$ has been counted exactly $k$ times by the above procedure.

We can start with choosing $a_1$, we can start with choosing $a_2$,..., we can start with choosing $a_k$.

This can be repaired by dividing by $k$.