I am doing a question from the textbook "Calculus and Statistics" by Gemigani.
If $n = 2m$ and $k= 1,2, \ldots ,m$
Prove that $C(n,k)= C(n,n-k)$
Ok so my approach begins with writing out the formula and substituting
$$\frac{n!}{k!(n-k)!} = \frac{n!}{(n-k)!(n-(n-k))!}$$
I am not sure where to go from here. How can I collapse the right hand side to equal the left hand side?
$\endgroup$ 42 Answers
$\begingroup$Algebraically, you are done, just notice the $(n-(n-k))$ simplifies to $n-n+k=k$. So your denominators are the same (just re-ordered).
Combinatorially, you can prove the identity by saying that the number of ways to choose $k$ people from $n$ is the same as the number of ways to "not choose" $n-k$ people from $n$. Essentially, you are going to mark each person as chosen or not. You either choose the $n-k$ to mark as not chosen (all the rest are chosen) or chose the $k$ to make as chosen and all the rest are marked as not chosen.
$\endgroup$ $\begingroup$For simplicity set $\alpha = n-k$. You get $\binom{n}{\alpha} = \frac{n!}{(n-\alpha)! \alpha!} = \frac{n!}{k! (n-k)!}$ since $n-(n-k) = k$.
$\endgroup$
