# proving and Identity combinatorially

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?

-

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.