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

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.