Show that $\binom{n}{k}$ equals to $\binom{n-1}{k}\cdot\frac{n-k+1}{k}$.

Question

It should be solved by using combinatorial proofs.

Answer 1

(As noted by juantheron, there is an error in the question title. It should be as it is in the body of this answer)

A classic method for combinatorial explanation of such equations usually uses counting the same thing in two different ways. This case,$$\binom{n}{k}=\binom{n}{k-1}\cdot\frac{n-k+1}{k}$$ is a simple example, as $\binom{n}{k} $ is the number of ways of choosing $k$ objects from a collection of $n$.

Another way to count the ways would be to first choose a collection of $k-1$ objects, leaving $n-(k-1)=n-k+1$. We can then take any of the $n-k+1$ remaining objects and add it to our collection, giving a collection of $k$ objects. But this method counts each such collection multiple times! Given any collection of $k$ objects, by first taking $k-1$ and then the remaining $1$, we see there are $k$ ways of getting the collection. Thus each such collection is counted $k$ times.

So we have a total of $$\binom{n}{k-1}\cdot\frac{n-k+1}{k}$$ $\binom{n}{k-1}$ for the ways to pick $k-1$ from $n$, multiplied by the $(n-k+1)$ ways to pick a $k^{th}$ element and the $1/k$ accounts for counting each possibility $k$ times.

So the number of ways to choose $k$ from $n$ is $\binom{n}{k-1}\cdot\frac{n-k+1}{k}$. But this is exactly $\binom{n}{k}$. Thus we arrive at the desired equality.