Is C(n,k) = C(n-2,k-2) + C(n-2,k-1) + C(n-2,k)

justaguide | College Teacher | (Level 2) Distinguished Educator

Posted on

The number of possible combinations when k elements are chosen from a total of n elements is C(n,k) = `(n!)/(k!*(n-k)!)`

C(n-2,k-2) + C(n-2,k-1) + C(n-2,k)

= `((n - 2)!)/((k-2)!*(n - k)!) + ((n - 2)!)/((k-1)!*(n - k - 1)!) + ((n - 2)!)/(k!*(n - k - 2)!)`

= `((n - 2)!)(1/((k-2)!*(n - k)!) + 1/((k-1)!*(n - k - 1)!) + 1/(k!*(n - k - 2)!))`

= `((n - 2)!)((k*(k-1))/(k!*(n - k)!) + (k*(n - k))/(k!*(n - k)!) + ((n-k-1)*(n-k))/(k!*(n - k)!))`

= `((n - 2)!)/(k!*(n-k)!)*((k*(k-1)) + (k*(n - k)) + ((n-k-1)*(n-k))`

= `((n - 2)!)/(k!*(n-k)!)*(k^2 - k + n*k - k^2 + n^2 - n*k - n*k + k^2 - n + k)`

= `((n - 2)!)/(k!*(n-k)!)*(n^2 - n*k + k^2 - n)`

As `n^2 - n*k + k^2 - n = n*(n-1)` only if k = 0 and for k = 0, the terms C(n-2, k-2) and C(n-2, k-1) are not defined C(n, k) `!=` C(n-2,k-2) + C(n-2,k-1) + C(n-2,k)

The statement C(n, k) =`` C(n-2,k-2) + C(n-2,k-1) + C(n-2,k) is false.

Sources: