2
$\begingroup$

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?

  • 0
    This w$a$s [asked and answered](http://math.stackexchange.com/questions/199289/combinatorially-prove-something) a few hours ago.2012-09-21

2 Answers 2

8

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.

0

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

  • 0
    Thanks, but as I said I can prove it using the binomial theorem too. We have to give a combinatorial proof.2012-09-21