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