$\sum_{k=0}^n 2^k {n \choose k}$

Question

I can't figure out this sum : $$\sum_{k=0}^n 2^k {n \choose k}$$ I tried writing out the first few terms and I reached : $1 + 2n + 2n(n-1) + \frac{4}{3}n(n-1)(n-2)$ at which point the pattern of $2$s broke and I can't find anything else to go with.

Answer 1

The answer is $3^{n}.$

The Binomial Theorem asserts that for real (or complex) $x, y$,

$$(x + y)^{n} = \sum_{k=0}^{n} {n\choose k}x^{k}y^{n-k}.$$

Plugging in $x = 2$ and $y = 1$ gives

$$(2 + 1)^{n} = 3^{n} = \sum_{k=0}^{n}{n\choose k}2^{k}1^{n - k} = \sum_{k=0}^{n}{n\choose k}2^{k},$$

which means $\sum_{k=0}^{n}{n\choose k}2^{k} = 3^{n}.$

Answer 2

If you try it for small values of $n$, and conjecture that it is in fact $3^n$ as given in the other answer, you can use a double-counting argument rather than pulling out a theorem (though the binomial theorem is quite a common one and good to know).

Let $S_n$ be a set of all the ways to paint $n$ distinguishable boxes either red, blue, or green. The obvious method is to go down the line and choose a color for each box; this is $n$ independent choices with 3 options each, and as each element of $S_n$ can be constructed in this way, we have $|S_n| = 3^n$ by rule of product.

Now consider a different way of choosing the colors. We know some amount of the boxes (from 0 to $n$ inclusive) will be "not-red". By rule of sum, we can partition the elements of $S_n$ based on how many boxes aren't red; that is, $|S_{nk}| = \sum_{k = 0}^n |S_n|$ where $S_{nk}$ is all the ways to paint $n$ boxes RBG with $k$ boxes not-red. If $k$ is fixed, then to count $S_{nk}$ requires us to first pick the $k$ boxes that will be not red, which costs us $\binom{n}{k}$. Then for these $k$ boxes, we again go down the list like before, this time independently choosing either blue or green for each box. This gives $2^k$ choices, so $|S_{nk}| = 2^k \cdot \binom{n}{k}$. Thus, $$3^n = |S_n| = \sum_{k = 0}^n 2^k \binom{n}{k}$$ This is certainly longer-winded than just applying the binomial theorem (though I put a finer point on the particulars than necessary), but this is frequently a useful combinatorial techinque for proving identities if you have a conjecture for what both sides look like.