Exercise C.1.6

Prove the identity

(nk)=nnk(n1k) \binom{n}{k} = \frac{n}{n-k}\binom{n-1}{k}

for 0k<n0 \le k < n.

(nk)=n!k!(nk)!=nnk(n1)!k!(n1k)!=nnk(n1k) \binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n}{n-k}\frac{(n-1)!}{k!(n-1-k)!} = \frac{n}{n-k}\binom{n-1}{k}