# 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

- NickLv 65 years agoBest 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.