combinatorics - A Combinatorial proof for $binom{n+1}{k}=frac{n+1}{k}binom{n}{k-1}$

The LHS counts the number of ways of choosing $k$ people from a group of $n+1$ people. The RHS first chooses $1$ person from $n+1$ people and then the remaining $k-1$ people from the remaining $n$ people. I just don't understand why is the RHS divided by $k$?

Answer

As you said, the LHS counts the number of ways of choosing $k$ people from a group of $n + 1$ people. On the RHS, there are $n + 1$ ways to choose a member of the group and $\binom{n}{k - 1}$ ways to choose the remaining members of the group. However, if we simply multiply those two factors, we will have counted the group $k$ times, once for each way we could select one of the $k$ people in the group first. Therefore, we need to divide by $k$ since the order in which the members of the group are selected does not matter.