Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer

Your Answer


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.