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

Question

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

I have no idea which story to form, I thought about $n$ students assuming n=4

picking 4 students for a committee with 3 roles. since each students has 3 options.

then on the other side.. $2^{0}\binom{4}{0} + 2^{1}\binom{4}{1} +2^{1}\binom{4}{2} + 2^{3}\binom{4}{3}+2^{4}\binom{4}{4}$ = $2^{0}\binom{4}{4} + 2^{1}\binom{4}{3} +2^{1}\binom{4}{2} + 2^{3}\binom{4}{1}+2^{4}\binom{4}{0}$

but im just stuck here...

Answer 1

HINT: You have a pool of $n$ students, and you want to divide them into $3$ groups, say Groups $1,2$, and $3$.

• One way is simply to assign each student to one of the groups. How many such assignments are there?
• Another way is first to select the students who are not going to be in Group $3$, and then to select a subset of them to be in Group $1$; the rest of the selected students will go in Group $2$. Of course the students who were not selected will be in Group $3$. You can split up this approach according to the number of students selected in the first step.

Answer 2

Define $A_n$ to be the set of strings of length $n$ made of $\{0, 1, 2\}$. It is clear that $|A_n| = 3^n$. We will prove that $|A_n| = \sum_{k=0}^n 2^{k}\binom{n}{k}$.

For $k=0, 1, \dots, n$ partition $A_n$ into $k+1$ disjoint sets $B_{n,k}$ each consisting of strings that contain exactly $k$ $2$s. It is clear that

$$ A_n = \bigcup_{k=0}^n B_{n,k} $$

and so

$$ |A_n| = \sum_{k=0}^n |B_{n,k}|\tag1. $$

Each element in $B_{n,k}$ is uniquely determined by the choice of $k$ positions on which to place a $2$ and a binary string on the remaining $n-k$ positions. Therefore, $|B_{n,k}| = 2^{n-k}\binom{n}{k}$. Substituting into $(1)$ and using $\binom{n}{k} = \binom{n}{n-k}$, we get

$$ |A_n| = \sum_{k=0}^n 2^{n-k}\binom{n}{k} = \sum_{k=0}^n 2^{k}\binom{n}{k}. $$

Answer 3

The "binomial theorem" says that $(x+ y)^n= \sum_{i=0}^n \begin{pmatrix}n\\ i\end{pmatrix} x^i y^{n-i}$. If x= 2 and y= 1 that becomes $(2+ 1)^n= \sum_{i=0}^n\begin{pmatrix}n \\i \end{pmatrix} (2^i)(1^{n-i})$ or $3^n= \sum_{i=0}^n \begin{pmatrix}n \\ i\end{pmatrix} 2^i$.