Exercise C.1.6 Prove the identity (nk)=nn−k(n−1k) \binom{n}{k} = \frac{n}{n-k}\binom{n-1}{k} (kn)=n−kn(kn−1) for 0≤k<n0 \le k < n0≤k<n. (nk)=n!k!(n−k)!=nn−k(n−1)!k!(n−1−k)!=nn−k(n−1k) \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} (kn)=k!(n−k)!n!=n−knk!(n−1−k)!(n−1)!=n−kn(kn−1)