prove nCk = n-2Ck + 2(n-2Ck-1) + n-2Ck-2 Please explain and show all steps. Thanks!?
- NickLv 64 years agoFavorite Answer
This could be considered a double application of Pascal's rule:
C(n,k) = C(n-1,k-1) + C(n-1,k)
= C(n-2,k-2) + C(n-2,k-1) + C(n-2,k-1) + C(n-2,k)
= C(n-2,k-2) + 2C(n-2,k-1) + C(n-2,k)
Also it could be considered a special case of the chu-vandermonde identity with i=2:
C(n,k) = C(n-i,k)C(i,0) + C(n-i,k-1)C(i,1) + C(n-i,k-2)C(i,2) + .. + C(n-i,k-i+2)C(i,i-2) + C(n-i,k-i+1)C(i,i-1) + C(n-i,k-i)C(i,i)
which counts the ways of choosing k people from n-i men and i women. The left hand side counts directly the choices of k people from n and the right counts the choices of k men and 0 women, k-1 men and 1 woman, k-2 men and 2 women etc.
- 4 years ago