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

Solution 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.