Prove that $k\binom{n}{k}=n\binom{n-1}{k-1}$

Question

I'm struggling to prove $$k\binom{n}{k}=n\binom{n-1}{k-1}$$

Here's what I'm doing:

$$k\binom{n}{k}=\frac{k\cdot n!}{k!(n-k)!}=\frac{k\cdot n\cdot(n-1)!}{k(k-1)!(n-k)!}=n\frac{(n-1)!}{(k-1)!(n-k)!}$$

I see the problem that in the denominator we have $(n-k)!$ I guess it should be $(n-(k-1))!=(n-k+1)!$ to make the whole fraction equal $n\binom{n-1}{k-1}$

What's the problem?

Answer 1

HINT Note that $$ n \binom{n-1}{k-1} = \frac{n (n-1)!}{(n-k)! (k-1)!} = \frac{n!}{(n-k)!} \times \frac{k}{k!} $$ Can you take it from here?

Answer 2

I have $n$ employees and will form a committee of $k$ people, one of whom serves as the president.

One way I could do this is to select the entire committee first, which can be done in $\binom{n}{k}$ ways. Once I've selected the committee, I can promote one person to president in $k$ ways, for a total of $k\binom{n}{k}$ ways of forming the committee.

Another way I could do this is to first choose a president from among all $n$ employees. From the remaining $n-1$ employees, I need to select an additional $k-1$ of them to serve in a non-presidential capacity. The second step can be done in $\binom{n-1}{k-1}$ ways, for a total of $n\binom{n-1}{k-1}$ ways of forming the committee.

Since both expressions count the same type of committee, they must be equal.

Answer 3

Your error is that you seem to think:

$$\binom{n-1}{k-1}=\frac{(n-1)!}{(k-1)!(n-k+1)!}\tag{wrong!}$$

We actually have that $(n-1)-(k-1)=n-k$, so:

$$\binom{n-1}{k-1}=\frac{(n-1)!}{(k-1)!((n-1)-(k-1)!}=\frac{(n-1)!}{(k-1)!(n-k)!}$$

So your proof was done!

A combinatorial approach

The left side counts the number of ways of picking $k$ distinct elements from $\{1,2,\dots,n\}$ and then selecting one of those $k$.

The right side counts the number of ways of picking one element from $\{1,\dots,n\}$ and then $k-1$ distinct from the remaining.

Show that these two numbers are the same.