Prove combinatorically - $\sum_{k=0}^{n} 2^{k}\binom{n}{k} = 3^{n}$ $\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...
 A: 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.

A: 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$.
A: 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}.
$$
