# 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 '14 at 0:47

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$.

-

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.

-

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

-

Both sides count the points in the graph of the relation "$\in$" on $X\times\mathcal P(X)$ when $X$ is an $n$-element set, which graph is the set $$\{\, (x,Y)\mid x\in X, ~ Y\subseteq X, ~ x\in Y\,\}.$$ The left hand side proceeds by choosing $x$ first (it occurs in $|\mathcal P(X\setminus\{x\})|=2^{n-1}$ subsets of $X$), while the right hand sides proceeds by choosing $Y\subseteq X$ first, and grouping the subsets by their size$~k$ (there are $\binom nk$ such subsets and each allows $k$ choices for $x$). You can call $Y$ the committee and $x$ the chairman if you like.

-