# Prove the identity $\sum_{k=0}^n \binom{n}{k}=2^n.$ using combinatorial proof [duplicate]

Prove the identity $\sum_{k=0}^n \binom{n}{k}=2^n.$ using combinatorial proof.

## marked as duplicate by Watson, Namaste, loup blanc, Martin Sleziak, user133281Sep 14 '16 at 13:40

• Set $\{1,\dots,n\}$ has $2^n$ subsets. How many of them have cardinality $k$? – drhab Sep 14 '16 at 10:41
• – Arnaud D. Sep 14 '16 at 10:45

Suppose you have $n$ distinct objects and you want to choose some (possibly none) of them.

One way to look at this is as follows. You can either select no object, or one object, or two objects, and so on, you can select all the $n$ objects. The number of ways of selecting $k$ objects is $\binom{n}{k}$, and as $k$ varies from $0$ to $n$, the total value is $$\sum_{k=0}^n\binom{n}{k}$$

Another way is to look at each object. For every object, you have two choices - either you choose it or you don't. Thus, for $n$ objects, you have $2^n$ choices, and by varying your choices, you can select any number of objects in any configuration.

As both the above refer to counting the number of ways of doing the same thing, they must be equal. So, $$\sum_{k=0}^n\binom{n}{k}=2^n$$

We have n objects. We can represent a selection of k objects from these n by a vector of n zeros or ones, eg (0 1 1 0 0) would represent picking objects 2 and 3 from 5.

We have 2 choices, 0 or 1, for each entries in such a vector so we have $2^{n}$ such vectors. This represents everything from picking no objects at all, (0 0 0 0 ... 0), all the way up to picking all n objects, (1 1 1 1 .... 1).

If we pick k objects from n then we have $\pmatrix{n \\ k}$ ways of doing that. If we consider k from 0 to n then we have $\sum_{k=0}^{n}\pmatrix{ n \\ k }$ possible choices. But this must equal the number of different vectors we have, $2^{n}$.

Therefore $2^{n} = \sum_{k=0}^{n}\pmatrix{n \\ k}$.

How many binary vectors of size $n$ there are?

We know that each bit has 2 options (0 or 1) so we have $2^n$ different binary vectors of size $n$.

On the other hand, if a binary vector has $k$ zeros then the other $n-k$ bits are ones, so we can divide to disjoint cases - "the vector has $k$ zeros" where $0\leq k \leq n$. How many binary vectors are there with $k$ zeros? - we can just pick the $k$ spots in the vector to put zeros and the rest of the bits are ones - so $n\choose k$. Sum the disjoint cases and youll get the number of all the binary vectors of size $n$.

Since both ways to count the size of the same set we get the equality.

Use the binomial theorem $(1+x)^n=\sum_{k=0}^n {n\choose k}x^k$, with $x=1$.

• I don't think this qualifies as "counting arguments"... – Arnaud D. Sep 14 '16 at 10:42
• But it involves factorials, which counting arguments don't. The counting argument proof is simply the statement of how many subsets does a set of n element have. – adamG Sep 14 '16 at 10:46
• The question is explicitly about the counting argument (it's mentionned 3 times). Your suggestion is of course correct, but it's not really what is asked. – Arnaud D. Sep 14 '16 at 10:49