# Combinatorial Proof with Summation Identity

Must show: $\sum_{i=0}^n i{n \choose i} = n2^{n-1}$ using a combinatorial argument. I have tried picking the problem apart by determining that the summation is equal to 1/2 of the size of all subsets of a set of size n times n. But I am having trouble relating that to what each term of the summation represents.

## 1 Answer

Hint: We have a group of $n$ people. They want to form a committee of $1$ or more people (so size is elastic), with a specified Chair. We count the number of ways to form a Committee-with-named-Chair in two ways.

First way: We pick a Chair ($n$ choices). For each choice, we pick a subset of the remaining $n-1$ people to join her on the Committee. If we count in this way, we will get the right-hand side of the identity.

Second way: We pick a group of $i$ people, $i=1$ to $n$, and they choose a Chair among them. If we count in this way, we will get the left-hand side of the identity.

• It really doesn't get much simpler than this. – Patrick Sep 29 '13 at 21:12