Prove $3^n = \sum_{k=0}^n \binom {n} {k} 2^k$

How do you derive $$\sum_{k=0}^n{n \choose k}=2^n?$$ For positive integer $n$

$$\sum_{k=0}^n{n \choose k}x^k=(1+x)^n$$

If you don’t know the binomial theorem, you can still prove it using a combinatorial argument.

$3^n$ is the number of $n$-letter strings that you can make using only $a$’s, $b$’s, and $c$’s; that counts them all at once, but we can count them in another way as well. One way to form such a string is to pick first which positions in the string won’t be $a$’s. If we decide to have $k$ letters that aren’t $a$’s, there are $\binom{n}k$ ways to decide where to put them; the other $n-k$ letters will of course be $a$’s. Then for each of those $k$ positions that won’t be occupied by $a$’s, we have to decide whether to put a $b$ or a $c$ there. That’s a two-way choice, and we have to make $k$ such choices independently, so there are $2^k$ ways to make these choices. Thus, there are altogether $\binom{n}k2^k$ strings that have a total of $k$ $b$’s and $c$’s. To get the total number of strings, just add up these numbers $\binom{n}k2^k$ for all possible values of $k$, i.e., for $k=0$ to $k=n$:

$$\sum_{k=0}^n\binom{n}k2^k\;.$$

Since this is just another way of counting the $n$-letter strings containing nothing but $a$’s, $b$’s, and $c$’s, it must be $3^n$.

It is $$\sum_{k=0}^n \binom{n}{k} 2^k \cdot 1^{n-k}=(1+2)^n$$

Here is a combinatorial interpretation:

The lefthand side counts functions from $[n]=\{1,2,\dots,n\} $ to $X=\{*,1,2\}$. We can count the left hand side a different way. Namely, it is the disjoint union over all $0 \leq k \leq n$ of functions $[n] \rightarrow X$ so that $k$ elements of $[n]$ get sent to $*$. Fixing a $k$, we have $n$ choose $k$ subsets that can be sent to $*$ and for the complement I must choose a function $[n] \rightarrow [2]$. Since there are $2^k $ of these, we recover $ 3^n = \sum_{k=0}^n\binom{n}{k}2^k$