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

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.)

• expand binomial $3^n=(2+1)^n$ – J. W. Tanner Feb 18 '20 at 3:39

## 2 Answers

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.

• Nice complement to my algebraic answer; +1 – J. W. Tanner Feb 18 '20 at 13:28

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?