Showing that $\sum_{k=1}^n \binom nk 2^{n-k} = 3^n - 2^n$

Question

I was wondering if there exist both symbolic/algebraic and combinatorial arguments justifying this identity:

$$\sum_{k=1}^n \binom nk 2^{n-k} = 3^n - 2^n$$

It came up while solving a probability problem, and as a rule I like to be able to resolve summations without always resorting to Wolfram|Alpha. (Working backwards, I can justify it as being a necessary term in the problem I'm solving for the answer to be correct, but this isn't particularly insightful.)

Answer 1

A combinatorical argument is, for example, the number of sequences of length $n$ with $1,2,3$ as possible entries: $3^n$.

Now, the number of all sequences not containing any $1$ amounts to $2^n$.

On the other hand you can count the number of sequences containing exactly $k$ $1$'s by $\binom{n}{k}2^{n-k}$.

So, the number of sequences containing at least one $1$ is $\sum_{k=1}^n\binom{n}{k}2^{n-k}$ which is equal to the number of all sequences minus those which contain no $1$: $\sum_{k=1}^n \binom nk 2^{n-k} = 3^n - 2^n$

Of course, the quicker algebraic argument is just using the binomial formula.

Answer 2

Using binomial expansion,

$$3^n=(2+1)^n=\sum_{k=\color{green}0}^n\binom n k 2^{n-k}=\binom n02^{n-0}+\sum_{k=\color{green}1}^n\binom n k 2^{n-k}.$$

Can you take it from here?