Combinatorial proof for $\sum_{k=0}^n 2^k \binom{n}{k} = 3^n$

Question

I have to prove the identity using a combinatorial proof:

$\displaystyle\sum\limits_{k=0}^n 2^k \binom{n}{k} = 3^n$

I think this should be my combinatorial proof:

We want to form a committee of $k$ people from a total of $n$ people. There are two ways of counting this committee.

1) Go through each member from the $n$ total people, and decide if they should be added to the committee or not, until we have reached $k$ people. This gives us the LHS.

...For the RHS, however, I am not sure how to form it. I think it should be something like forming subsets of $3$ people and choosing from that, but I'm not sure how that will form the same committee as the LHS.

EDIT: Okay, I also had the idea of forming a ternary string, and I could get the RHS this way. But I was not sure about the LHS. But the first answer gave me the right idea. Thanks a lot.

Answer 1

We want to form $n$-letter words over the alphabet $\{a,b,c\}$. There are $3^n$ such words.

To count these words in another way, take a fixed $k$, where $0 \le k \le n$. To make an $n$-letter word with a total of $k$ $a$'s and/or $b$'s, choose the $k$ positions that will have $a$ and/or $b$. This can be done in $\binom{n}{k}$ ways. For each such way, these $k$ positions can be filled with $a$'s and/or $b$'s in $2^k$ ways, for a total of $2^k \binom{n}{k}$ ways. For each of these $2^k\binom{n}{k}$ ways, there is only one way to put in the $c$'s. Finally, add up, $k=0$ to $n$.

Answer 2

Hint: Remember that $3^n$ is the number of ways to put a set of $n$ distinct things into an array of $3$ containers. Likewise, $2^n$ is the number of ways to put a set of $n$ distinct things into an array of $2$ containers.

Answer 3

While you are not looking for an algebraic proof, the algebraic proof using the binomial theory is tempting...

$\sum_{k=0}^{n} \binom{n}{k} (1+1)^{k}.1^k=(2+1)^n$

Answer 4

There is a nice double counting proof, from the geometric point of view. Consider all faces of a n-cube. These faces can be encoded by a sequence of "0", "1" and a "*", where the star signifies that the coordinate can be either 0 or 1 in the face. This immediately gives $3^n$ faces. On the other hand, the number of $k$-dimensional faces is equal to $\binom{n}{k}$ way of choosing $k$ coordinates times $2^{n-k}$ ways of fixing the remaining coordinates, all summed over all $k=1..n$. Of course, this proof is actually equivalent to that by Andre above.

P.S. This is actually Example 8.3 in my discrete geometry book (sorry for the shameless plug - much of the book is about something else).