# Prove an equality using combinatorial arguments

$$n \cdot {2^{n - 1}} = \sum\limits_{k = 1}^n {k\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array}} \right)}$$

The left-hand side can describe the number of possibilities choosing a committee with one chairman. How can the right-hand side feet to this story?

-

Hint. The left hand side counts the number of possibilities of choosing the committee in this way:

(1) choose the chairman;

(2) choose the rest of the committee from the remaining $n-1$ people.

But you could also do it this way:

(1) choose a committee of $k$ people;

(2) choose the chairman from this committee;

and then realise that there are various possibilities for $k$. See if you can fill in the details.

-
thanks, I just realized that! –  AndrePoole Feb 5 at 0:47

The right side represents the numer of possibilities of choosing a chairman of a k-element committee - it can consist of 1,...,k,...,n members, and from every situation you can choose the chairman on ${k \choose 1}$ ways.

-

Easier is to do this algebraically:

$$(1+x)^n= \sum\limits_{k=0}^{n} {n \choose k}x^k.$$

Now differentiate both sides with respect to $x$ and set $x=1$.

-
It is equivalent because for each group with the size of $k$ we can choose $k$ different chairmans.