2
$\begingroup$

How would I simplify $${n\choose k} - {n-1 \choose k}$$

I've expanded them into the binomial coefficient form $$\frac{n!}{k!(n-k)!} - \frac{(n-1)!}{k!(n-1-k)!}$$

but that's about all I've got.

I'm having trouble with factorials. Any suggestions?

$\endgroup$
  • $\begingroup$ Note that the denominator should have $(n-k)!$ not $(n-k!)$ $\endgroup$ – qwr Jun 30 at 4:51
5
$\begingroup$

To explain why your expression is equal to ${n - 1 \choose k - 1}$ combinatorially, note that to choose $k$ out of $n$ objects entails one of two things:

  1. You choose the first object and $k - 1$ objects from the remaining $n - 1$ objects. Clearly, there are ${n - 1 \choose k - 1}$ ways to choose $k$ objects like this.

  2. You don't choose the first object, meaning you must choose $k$ objects from the remaining $n - 1$ objects. Here there are $n - 1 \choose k$ ways to do this.

Hence, $${n - 1 \choose k} + {n - 1 \choose k - 1} = {n \choose k}$$ from which the equality in other answers follows.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I love this explanation! Very intuitive. Thank you +1 $\endgroup$ – dafinguzman Jun 30 at 3:32
5
$\begingroup$

You can write it as $$\frac{(n-1)!}{k!(n-k-1)!}\left[\frac{n}{n-k}-1\right]=\frac{(n-1)!}{(k-1)!(n-k)!}=\binom{n-1}{k-1}$$

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

Use the fact that $$\binom n k = \binom {n - 1}{k - 1} + \binom {n - 1} k$$ for all integers $1 \leq k \leq n - 1.$

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

To expand on Anurag A's answer:

When working with combinatorial identities, $n!$ and $(n-1)!$ are actually almost the same, in that $(n-1)! \times n = n!$, i.e. they differ only by a factor of $n$. The same fact can be applied to see the slightly less obvious fact that $(n-k)!$ is just $(n-k-1)! \times (n-k)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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