Find ${n\choose0} + 2{n\choose1}+ 2^2{n\choose2}+...+2^n{n\choose n} = \sum_{k=0}^{n}{n\choose k}2^k$ 
Find ${n\choose0} + 2{n\choose1}+ 2^2{n\choose2}+...+2^n{n\choose n} =
 \sum_{k=0}^{n}{n\choose k}2^k$

Calculating the first couple of sums it seems that the answer is $3^n$, but I am having trouble arriving at it. I noticed that the above sum is the number of subsets of every subset of a set with $n$ elements, for example if you have the set $\{1,2,...,n\}$ the sum will count the subsets of $\{1,2,3\},\{1,2,3,4\}$ and so on and I already know that $3^n$ is the number of ternary sequences of length $n$ and I tried establishing a bijection between these two sets but to no avail. 
Any suggestions? Would appreciate combinatorial proofs (that is proofs in which something is counted), instead of purely algebraic ones, but would settle for both. Thanks.
 A: It is easy to see that there are $3^n$  "words" of length $n$ over the alphabet A, B, C. We now count the words in a different way. 
Consider the words that have a total of $k$ occurrences of the letters A and/or B. The $k$ places to be occupied by A's or B's can be chosen in $\binom{n}{k}$ ways, with the rest occupied by C. For each such choice, there are $2^k$ ways to fill these spaces with A's and/or B's, for a total of $\binom{n}{k}2^k$. Now add up over all $k$.
A: Hint: use the binomial theorem with $$\sum\limits_{k=0}^n \binom{n}{k}2^k=\sum\limits_{k=0}^n \binom{n}{k}2^k\cdot 1^{n-k}=\dots$$
Can you take it from here?
A: Remember the binomial theorem:
$$(a+b)^n=\sum\limits_{k=0}^n {n\choose k}a^k b^{n-k}$$
Let $a=2$, $b=1$ and you'll find your guess is correct.
A: Hint: Do you know the binomial formula? Consider
$$(1 + 2)^n$$
A: For a combinatorial approach, consider the number of ways to choose taking $n$ books to 2 holidays: Either I'm not taking a book, or I'm taking a book to the first holiday, or I'm taking a book to the second holiday (but not both).
The binomial coefficient considers the number of ways to choose $k$ books out of $n$ books to take on some holiday. The power considers for each book whether I take it to the first or the second holiday.
On the other hand, for each book there are three possibilities, either I take it to no holiday, or to holiday 1, or to holiday 2. There are $n$ books. This gives $3^n$ ways to choose books in this manner.
Therefore your expression equals $3^n$.
