<s>[INST] 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...
 [/INST] 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}.
$$
</s>