Combinatorial Proof Help?

Give a combinatorial proof that C(n,k) - C(n-2,k) = C(n-1,k-1) + C(n-2,k-1)

1 Answer

Relevance
  • Nick
    Lv 6
    5 years ago
    Best Answer

    C(a,b) is the sum of the choices of b objects from a which include the first object C(a-1,b-1) and those that don't C(a-1,b):

    C(a,b) = C(a-1,b-1) + C(a-1,b) <----

    eg.

    ■|□■...□■■ -------- choices that include first object C(a-1,b-1)

    □|■■...□■■ -------- choices that don't include first object C(a-1,b)

    □=unchosen (a-b)

    ■=chosen (b)

    Repeated use of the formula for a=n, b=k:

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

    then for the second term a=n-1, b=k:

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

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

    Note: we could have used the same argument replacing inclusion/exclusion of the first object with any one of the n objects.

Still have questions? Get your answers by asking now.