Simplifying ${n\choose k} - {n-1 \choose k}$.

Question

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?

Answer 1

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.

Answer 2

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}$$

Answer 3

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

Answer 4

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