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