4
$\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$
1
  • $\begingroup$ Note that the denominator should have $(n-k)!$ not $(n-k!)$ $\endgroup$
    – qwr
    Commented Jun 30, 2020 at 4:51

4 Answers 4

7
$\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.

$\endgroup$
1
  • $\begingroup$ I love this explanation! Very intuitive. Thank you +1 $\endgroup$ Commented Jun 30, 2020 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}$$

$\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.$

$\endgroup$
1
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)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .