Prove that if n and k are integers with 1 ? k ? n, then a)

Chapter 9, Problem 21E

(choose chapter or problem)

Prove that if \(n\) and \(k\) are integers with \(1 \leq k \leq n\), then \(k\left(\begin{array}{l}n \\ k\end{array}\right)=n\left(\begin{array}{c}n-1 \\ k-1\end{array}\right)\),

a) 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.]

b) using an algebraic proof based on the formula for \(\left(\begin{array}{l}n \\ r\end{array}\right)\) given in Theorem 2 in Section 6.3.

Equation Transcription:

Text Transcription:

n

k

1 \leq k \leq n

k (n \\ k)=n(n-1 \\ k-1)

k

n

(n \\ r)