0
$\begingroup$

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

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

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.

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

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.