113 views

Prove that if $n$ and $k$ are integers with $1 \leq k \leq n,$ then $k \binom{n}{k} = n \binom{n−1}{k−1},$

1. using a combinatorial proof. [Hint: Show that the two sides of the identity count the number of ways to select a subset with $k$ elements from a set with $n$ elements and then an element of this subset.]
2. using an algebraic proof based on the formula for $\binom{n}{r}$ given in Theorem $2$ in Section $6.3.$