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

Question

How would I prove that $3^n = \sum_{k=0}^n \binom {n} {k} 2^k$ for any positive integer $n$?

Answer 1

Hint: $3^n=(2+1)^n{}{}{}{}{}$.

Answer 2

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

Answer 3

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

Putting $x=2$ gives you your answer.

See combinatorial proof of binomial theorem http://www.math.hmc.edu/calculus/tutorials/binomial_thm/combinatorial.pdf