Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

marked as duplicate by Byron Schmuland, 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.

This was asked and answered a few hours ago. – André Nicolas Sep 21 '12 at 2:47
up vote 4 down vote accepted

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.

share|cite|improve this answer

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}$

share|cite|improve this answer
Thanks, but as I said I can prove it using the binomial theorem too. We have to give a combinatorial proof. – rafidhoda Sep 21 '12 at 2:49

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