Possible Duplicate:
Proving a special case of the binomial theorem

Prove the identity using a combinatorial argument: $$\sum_{k=0}^{n}\binom{n}{k} = 2^{n}$$

I'm not sure how to do a combinatorial argument so any help is appreciated. All I know is that $2^{n}$ is representing the number of elements in the power set of n.


marked as duplicate by J. M. is a poor mathematician, Ross Millikan, anon, Douglas S. Stones, davidlowryduda Aug 1 '12 at 6:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


A combinatorial argument is one that establishes an equality by counting the same things two different ways. You have done one side already-as you say, $2^n$ is the number of subsets of a set of size $n$. Hint: think about categorizing the subsets by their size-does that help you with the other side of the equality?

  • $\begingroup$ So is expanding the series to something like C(n,0) + C(n,1) +...+ C(n,k) along the right track? $\endgroup$ – Jason Curt Aug 1 '12 at 3:43
  • $\begingroup$ Yes, that's heading the right way. Think about what $\binom{n}{k}$ means... $\endgroup$ – Luke Mathieson Aug 1 '12 at 3:46

Consider a set of $n$ distinct objects. How many subsets does this set have?

The question can be answered in $2$ different ways.

Method 1

Subsets of the original set include the empty set, subsets with one and only one element, subsets with two and only two elements, ... , subsets with $n-1$ and only $n-1$ elements and subsets with $n$ and only $n$ elements.

The number of empty sets is $1= \binom{n}{0}$

The number of different subsets with $r$ and only $r$ element is $\binom{n}{r}$ (constructed by choosing which $r$ elements are in the subset) for each $r = 1,2, ... , n$

Summing up all the terms we get the total number of subsets $\sum_{r=0}^{n} \binom{n}{r}$

(The thing to note here is that none of the subset is counted twice within a term or among the terms of the finite sum)

Method 2

We use a choice function to construct all the different subsets. Assume the elements are numbered $1$ to $n$ (this can be done since the objects are distinct) Now to construct a subset out of these n objects, we should choose which objects to be included in the subset. So, for each object there is a choice of 'IN' or 'OUT' of the subset. Depending on whether the first object is 'IN' or 'OUT' we have a set of subsets, depending on whether the second object is 'IN' or 'OUT' we have a set of subsets, and so on. But observe that the choice 'IN' or 'OUT' of the $r^{th}$ object does not depend on the choices made for the other $n-1$ objects.

Therefor by the multiplication principle there are $2 \times 2 \times ... \times 2 $ ($n$ $2$'s) $=2^n$ subsets.

Method 1 and 2 should yield the same answer. Hence the result follows.


Not the answer you're looking for? Browse other questions tagged or ask your own question.