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?

It's taken from Introduction to Probability by Blitzstein and Hwang, I've tended to trust the book so far :) — alekscooper, Apr 05 '17 at 15:01
I think he is talking about your last sentence, not the problem in the book... — gt6989b, Apr 05 '17 at 15:01
There is no problem with your solution: ${n-1 \choose k-1}=\frac{(n-1)!}{(k-1)!(n-k)!}$ — Arnaldo, Apr 05 '17 at 15:08
Not sure I understand the questions :) * is multiplication, and the last sentence is my attempt to follow the formula for $n\binom{n}{k}$ — alekscooper, Apr 05 '17 at 15:08
In the denominator you must have $(n-1-(k-1))$, which is precisely $(n-k)$. — Felicio Grande, Apr 05 '17 at 15:10
@Arnaldo Ok, I see now, I should have applied the formula, not my 'common sense' that failed me :) — alekscooper, Apr 05 '17 at 15:10
So many duplicates: http://math.stackexchange.com/q/2047226/215011 , http://math.stackexchange.com/q/528927/215011 , http://math.stackexchange.com/q/984998/215011 — grand_chat, Apr 05 '17 at 15:16

Thomas Andrews · Answer 1 · 2017-04-05T15:23:11.400

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.

score 1 · Accepted Answer · answered Apr 05 '17 at 14:59

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?

answered Apr 05 '17 at 14:59

gt6989b

54,422

Yes, I can :) Problem solved, I guess :) – alekscooper Apr 05 '17 at 15:11

score 1 · Answer 3 · answered Apr 05 '17 at 15:04

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.

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

3 Answers3