Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

So i'm not sure at all how to prove things using a combinatorial proof. Where to do i start? What do i need to think about etc. For example how would i prove

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

share|improve this question
Two approaches here: - Sums like this often lend themselves to induction. - If you stare hard at this, you may see a connection to the binomial theorem. – Johannes Kloos Sep 19 '12 at 19:14
1  
For this particular target, remember that $3=1+2$ and use the binomial theorem. But unless you restrict yourself to an extremely restricted class of problem, I don't think that very specific general instructions for how to devise a proof can be given. – Henning Makholm Sep 19 '12 at 19:15
FYI, it's combinatorial, not combinatorical. @JohannesKloos: I wouldn't consider either of your approaches to be combinatorial. While they are valid methods of proof, it is often important to a student learning combinatorics to specifically learn how to give combinatorial (aka bijective) proofs. – Michael Joyce Sep 19 '12 at 19:24
@MichaelJoyce: True, I missed the "combinatorial" bit. – Johannes Kloos Sep 19 '12 at 19:55
1  
@MichaelJoyce: I would nuance the remark about learning combinatorics. I think it is OK to give an algebraic proof first if one easily spots one. Then looking closely to the proof, there is often a bijective proof hidden beneath the algebraic proof, as would be the case here when using the binomial theorem. Seeing how the two are related is more instructive than being forced to forgo the algebraic proof since "it must be bijective". – Marc van Leeuwen Sep 20 '12 at 6:47

1 Answer

up vote 3 down vote

The general strategy is to count the same thing in two different ways. But this is too general a recipe to be truly useful. The devil is in the details: What shall we count in two different ways?

In our case, $3^n$ is the number of $n$-letter words in the alphabet $\{a,b,c\}$.

These words can be also counted as follows. Choose the $i$ places that will get an $a$ or a $b$. There are $\dbinom{n}{i}$ ways to do this.

For each such choice there are $2^i$ ways to fill the chosen places with $a$'s and/or $b$'s. So $\dbinom{n}{i}2^i$ counts the words that have a total of $i$ $a$'s and/or $b$'s, or equivalently the number of words that have $n-i\,$ $c$'s.

Now add up, $i=0$ to $n$. This counts all the words.

share|improve this answer
lets say n = 2, So we have a set with 9 words { ab,ac,bc,ba,ca,cb,aa,bb,cc}.. We have the sum of (2 choose 0)*2^0 + (2 choose 1)2^1 + (2choose 2)*2^2, Can you explain which words go in which expression in the sum ? – Thatdude1 Sep 20 '12 at 19:57
$i=0$: $cc$; $i=1$: $ac$, $ca$, $bc$, $cb$; $i=2$: $aa$, $ab$, $ba$, $bb$. Generally, as described in the answer, for given $i$ we use the words that have the number of occurrences of $c$ equal to $n-i$. – André Nicolas Sep 20 '12 at 20:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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