Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

prove the Identity:

(n-k)$\binom nk$ = n$\binom {n-1}k$

I have proven it algebraically but now I need to prove it combinatorially ( count something in two ways).

Here is my attempt:

theorem: P(n,k) = $\frac {n!} {n-k!}$

theorem: C(n,k) = $\frac {n!} {k!(n-k)!}$

P(n,k) = C(n,k) * P(n-k,1)

P(n,K) = C(n,k) * $\frac {(n-k)!} {(n-k-1)!}$

P(n,K) = C(n,k) * $\frac {(n-k)(n-k-1)!} {(n-k-1)!}$

P(n,k) = c(n,k) * (n-k)

P(n,k) = $\frac {n!} {k!(n-k)!}$ * (n-k)

P(n,k) = (n-k)*$\binom nk$

^^ i have proven one part of the identity,

but I do not know how to prove it in the other way: n$\binom {n-1}n$

any help?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

How many ways are there to choose a set of $j$ elements from a set of $n$ elements, as well as $1$ special element from the set of $j$ elements?

If we choose the set of $k$ elements first, there are $\binom{n}{j}$ sets possible and $j$ choices for the special element, so the number of ways is $j\cdot\binom{n}{j}$.

If we choose the special element first out of the $n$, we have to choose $j-1$ more from the $n-1$ remaining elements to get the entire $j$-set. Thus the number of ways is $n\cdot \binom{n-1}{j-1}$. So then $$ j\cdot\binom{n}{n-j}=n\cdot\binom{n-1}{n-j} $$ Let $j=n-k$ to recover your identity.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.