Question

Find how many committees with a chairman can be chosen from a set of n persons. Derive the identity $(\frac{n}{1})+2(\frac{n}{2})+3(\frac{n}{3})+\cdots +n(\frac{n}{n})=n{2}^{n-1}.$

• A. $n{(1+x)}^{n-1}=(\frac{n}{1})+2(\frac{n}{2})x+\cdots +(n-1)(\frac{n}{n-1})x^{n-2}+n(\frac{n}{n})x^{n-1}.$
• B. $n{(1-x)}^{n-1}=(\frac{n}{1})+2(\frac{n}{2})x+\cdots +(n-1)(\frac{n}{n-1})x^{n-2}+n(\frac{n}{n})x^{n-1}.$
• C. $n{(1+x)}^{n+1}=(\frac{n}{1})+2(\frac{n}{2})x+\cdots +(n+1)(\frac{n}{n-1})x^{n-2}+n(\frac{n}{n})x^{n-1}.$
• D. $n{(1-x)}^{n-1}=(\frac{n}{1})+2(\frac{n}{2})x+\cdots +(n-1)(\frac{n}{n+1})x^{n-2}+n(\frac{n}{n})x^{n-1}.$

Answer 1

The correct option is A $n{(1+x)}^{n-1}=(\frac{n}{1})+2(\frac{n}{2})x+\cdots +(n-1)(\frac{n}{n-1})x^{n-2}+n(\frac{n}{n})x^{n-1}.$

The number of persons in the committee may vary between 1 and n. Let us count how many such committees number k persons.The k persons can be chosen in $(\frac{n}{k})$ ways while the chairman can be chosen in k ways, yielding a total of $k(\frac{n}{k})$ committees with k persons.Adding up for k=1, 2, ..., n, we see that the total number of committees is $(\frac{n}{1})+2(\frac{n}{2})+3(\frac{n}{3})+\cdots +n(\frac{n}{n}).$On the other hand, we can first choose the chairman. This can be done in n ways.Next, we choose the rest of the committee, which is an arbitrary subset of the remainingn-1 person. Because a set with n-1 elements contains $2^{n-1}$ subsets, itfollows that the committee can be completed in $2^{n-1}$ ways and the total number of committees is $n{2}^{n-1}.$ Observation There are many proofs of the given equality. An interesting one is the following. Consider the identity ${(1+x)}^n=1(\frac{n}{1})x+(\frac{n}{2})x^{{}^2}+\cdots +(\frac{n}{n-1})x^{n-1}+(\frac{n}{n})x^n.$ Differentiating both sides with respect to x yields $n{(1+x)}^{n-1}=(\frac{n}{1})+2(\frac{n}{2})x+\cdots +(n-1)(\frac{n}{n-1})x^{n-2}+n(\frac{n}{n})x^{n-1}.$Setting x=1 gives the desired result.