3
$\begingroup$

I need to proof the following : $\binom{n}{k}=\frac{n}{k}*\binom{n-1}{k-1}$ using combinational proof only

The main problem is the division in $k$, I'll be glad if someone could provide an explanation for division in $k$.

This is what I've done

  • Problem

: choose a group of $k$ people from $n$ people

  • Left

: $\binom{n}{k}$ - to choose k from n people. (definition)

  • Right

$\binom{n-1}{k-1}$ - choose $k-1$ people from $n-1$. $$$$ $\frac{n}{k}$ - $n$ choose the first person to be in the group,$k$ umm, I don't know.

I think when I use the term first person in the group I created order in group and the group shouldn't have an order, yet I'm not sure how I defined it like how does the order looks, if someone could explain how to choose the first person cause order in the group and add a simple example so I'll understand how choosing the first person cause order I'll be very happy.

Any help will be appreciated, Thanks.

$\endgroup$
  • 7
    $\begingroup$ Prove that $$ k \binom{n}{k} = n \binom{n - 1}{k - 1}$$ instead. $\endgroup$ – Trevor Gunn Nov 23 '17 at 17:17
2
$\begingroup$

Suppose we are choosing a team of $k$ people from $n$ candidates. The team will have exactly one captain.


To count the number of possible teams, we could select the $k$ team members first, then from those $k$ members we choose the captain. This gives

$$\binom{n}{k}\cdot\binom{k}{1}\ =\ \binom{n}{k}\cdot k$$ configurations.

Another way to count these would be to first select the captain from the original $n$ people, then select the remaining $k-1$ team members from the $n-1$ remaining people. There are

$$\binom{n}{1}\cdot\binom{n-1}{k-1}\ =\ n\cdot\binom{n-1}{k-1}$$

such configurations.


These two methods of counting yield

\begin{align} \binom{n}{k}\cdot k\ &=\ n\cdot\binom{n-1}{k-1}\\\\ \binom{n}{k} &=\frac{n}{k}\cdot\binom{n-1}{k-1}. \end{align}

Note that division is okay here since the requirement that there be a captain means that $k>0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.