I need to prove that $$\sum\limits_{k=0}^{n}2^k \binom{n}{k}=3^n$$
for any integer $n$. Induction seems to be the straightforward solution, but I have failed at it:
\begin{align} \sum\limits_{k=0}^{n}2^k \binom{n}{k}=\\\sum\limits_{k=0}^{n-1}2^k \binom{n}{k}+2^n=\\ \sum\limits_{k=0}^{n-1}2^k \binom{n-1}{k}\frac{n}{n-k}+2^n=\\ \sum\limits_{k=0}^{n-1}2^k \binom{n-1}{k}\left(1+\frac{k}{n-k}\right)+2^n=\\ 3^{n-1}\sum\limits_{k=0}^{n-1}2^k \binom{n-1}{k}\frac{k}{n-k}+2^n=\\ \end{align}
The last step is the induction hypothesis and the base of induction is trivial. I'm not sure what to do next.
There might also be a combinatorical proof: the expression on the left is the amount of ways to pick some balls out of $n$ balls and color each one of them in either of 2 colors. However, I do not follow how that is equal to $3^n$.
Here's an argument using the binomial expansion, which can be proven using induction or other arguments: $$(1 + x)^n = \sum_{k=0}^n\binom{n}{k}x^k \qquad \forall x \in \mathbb{C}$$ Let $x = 2$ to get your answer.