Prove the combinatorial identity $$\sum_{k=1}^{n}k\cdot {n\choose k}=n\cdot 2^{n-1} $$
I got this proof.
Suppose we are given $n$ distinct people. Now, consider the no. of teams with a team leader.
The RHS says " fix the team leader ( we can do it in $n$ ways) and then find all possible teams under that leader ( $2^{n-1}$ teams).
Note that $$k\cdot {n \choose k}=k\cdot \frac{n!}{k!(n-k)!}=\frac{n!}{(k-1)!(n-k)!}=n\cdot {n-1\choose k-1} $$
So, the LHS says " fix the team leader we can do it in $n$ ways) and then find all possible teams of size $k$ under that leader which we can do in ${n-1\choose k-1} $ ways and then we sum it up over all possible $k$."
This proof was different from the given proof in the book. So can someone once proof read it?
Thanks in advance.
Best Answer
As noted in the comment, what you have done is algebraically correct, but it is just a few steps away from the expression on the RHS, since $$\sum_{k=1}^n \binom{n-1}{k-1} = \sum_{k=0}^{n-1} \binom{n-1}{k} 1^k 1^{n-1-k} = (1+1)^{n-1} = 2^{n-1}.$$ So I think you would agree that there is something of the combinatorial flavor of your proof that has been lost by performing the manipulation $$k \binom{n}{k} = n \binom{n-1}{k-1}, \tag{1}$$ as now both sides of the equation have the interpretation of first choosing the team leader in one of $n$ ways.
By contrast, the solution proposed in the comment (and probably your textbook as well), notes more directly that $k \binom{n}{k}$ counts the number of teams of size $k$, in which there are $k$ distinct choices for the team leader. Thus the total number of teams is simply the sum of all $k$-size teams as $k = 1$ to $n$.
What the combinatorial argument boils down to is that the enumeration on the RHS first selects the leader, then finds the number of teams of any size that can be selected; whereas the LHS first selects the team size, counts the number of such teams without regard to identifying the leader--leading to the expression $\binom{n}{k}$--then identifies one member as the leader which leads to $k \binom{n}{k}$ teams of size $k$. What makes your algebraic identity $(1)$ interesting is that it itself has a combinatorial interpretation: the LHS is what we had just discussed, but the RHS corresponds to first selecting a leader among the $n$ people, then filling out the remaining $k-1$ team members among the $n-1$ people remaining, to form the full team of size $k$.