Combinatorial proof help 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. 
 A: 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$.
A: 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).  
A: 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.
A: 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$
