Combinatorially prove that $\sum_{i=0}^n {n \choose i} 2^i = 3^n $

Question

So I'm not sure at all how to prove things using a combinatorial proof. Where to do I start? What do i need to think about etc. For example how would i prove

$$\sum_{i=0}^n {n \choose i} 2^i = 3^n $$

Answer 1

The general strategy is to count the same thing in two different ways. But this is too general a recipe to be truly useful. The devil is in the details: What shall we count in two different ways?

In our case, $3^n$ is the number of $n$-letter words in the alphabet $\{a,b,c\}$.

These words can be also counted as follows. Choose the $i$ places that will get an $a$ or a $b$. There are $\dbinom{n}{i}$ ways to do this.

For each such choice there are $2^i$ ways to fill the chosen places with $a$'s and/or $b$'s. So $\dbinom{n}{i}2^i$ counts the words that have a total of $i$ $a$'s and/or $b$'s, or equivalently the number of words that have $n-i\,$ $c$'s.

Now add up, $i=0$ to $n$. This counts all the words.