# Prove $\sum_{k=0}^{n}\binom{n}{k} = 2^{n}$ combinatorially [duplicate]

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., Ross Millikan, anon, Douglas S. Stones, mixedmath♦Aug 1 '12 at 6:01

like this or this? – anon Aug 1 '12 at 3:38
@Jason Curt: Please why are you asking two similar question differently? You have the chance to marge the two questions together. Take a look at this (math.stackexchange.com/questions/177405/… ). – Hassan Muhammad Aug 1 '12 at 5:25

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?

-
So is expanding the series to something like C(n,0) + C(n,1) +...+ C(n,k) along the right track? – Jason Curt Aug 1 '12 at 3:43
Yes, that's heading the right way. Think about what $\binom{n}{k}$ means... – 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.

-