Possible Duplicate:
Combinatorially prove something

I have to give a combinatorial proof of the identity: $$\sum_{i=0}^{n}{\binom{n}{i}}{2^i}=3^n$$

I can use prove it using the binomial theorem but not sure how to start for a combinatorial proof. Any help?


marked as duplicate by user940, Aang, tomasz, Chris Eagle, William Sep 27 '12 at 7:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Consider it as we are choosing $i$ people for a committee, from a total of $n$ people. This can be done in $\displaystyle {n \choose i}$ ways.

After we've chosen that, we would like to choose a super-committee. For each of the $i$ people, we decide whether they stay on the committee or go on to the super-committee (but they are not on both the super-committee and the committee). This can be done in $2^i$ ways.

Summing over all $i$ gives the total number of ways this can be done as: $\displaystyle \sum_{i=0}^n {n \choose i}2^i$.

Now we count this in a different way. For each person this gives 3 options: be on neither the super-committee nor the regular committee, be on the committee, or be on the super-committee.

So we have 3 options per person for a total of $3^n$ outcomes, and so

$\displaystyle \sum_{i=0}^n {n \choose i}2^i = 3^n$,

as desired.


Consider : $(1+x)^n=\sum_{i=0}^{n}\binom{n}{i}x^{i}$

sub $x=2$

we have , $3^{n}=(1+2)^n=\sum_{i=0}^{n}\binom{n}{i}2^{i}$

  • $\begingroup$ Thanks, but as I said I can prove it using the binomial theorem too. We have to give a combinatorial proof. $\endgroup$ – rafidhoda Sep 21 '12 at 2:49

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