The combinatorial proof is to prove that
$$\sum_{k=1}^n k\cdot{n \choose k} = n\cdot 2^{n-1}$$
The solution says to count the leader and committee in two ways.
The first way you choose the leader in n diff ways. Then choose the rest of the committee in $2^{n-1}$ ways to get the second side of the equation.
The second way you choose a committee with $k$ people in ${ n \choose k}$ ways, and then there are $k$ ways to choose its leader.
So this is suppose to give you the left side of the equation
$$ \sum_{k=1}^n k\cdot{n \choose k} = n\cdot 2^{n-1}$$
What I'm not understanding is why in the second part, you use a Riemann's sum to add all the ways. Because if you're just choosing $k$ people, I'm not sure why the $k$ value has to increase.
Thanks.
No comments:
Post a Comment