Combinatorial proof of the identity $\sum\limits_{i=0}^{n}{\binom{n}{i}}{2^i}=3^n$

Question

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?

Answer 1

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.

Answer 2

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