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

  • 1
    $\begingroup$ 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. $\endgroup$ – Johannes Kloos Sep 19 '12 at 19:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Henning Makholm Sep 19 '12 at 19:15
  • $\begingroup$ 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. $\endgroup$ – Michael Joyce Sep 19 '12 at 19:24
  • $\begingroup$ @MichaelJoyce: True, I missed the "combinatorial" bit. $\endgroup$ – Johannes Kloos Sep 19 '12 at 19:55
  • 1
    $\begingroup$ @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". $\endgroup$ – Marc van Leeuwen Sep 20 '12 at 6:47

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.

  • $\begingroup$ 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 ? $\endgroup$ – Thatdude1 Sep 20 '12 at 19:57
  • $\begingroup$ $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$. $\endgroup$ – André Nicolas Sep 20 '12 at 20:06

Late answer but I thought a binomial theorem approach was pretty neat too. I think someone in the comments mentioned it. I also know op asked for a combinatorial proof but I noticed that after writing this so I will leave it anyway as a point of interest.

Recall the binomial theorem:

$$ (x+y)^n = \sum_{i=0}^n{n \choose i}x^{n-i}y^i $$

To get the rhs to match your question, we can let $x=1$ and $y = 2$ giving us:

$$ \begin{align} (1+2)^n &= \sum_{i=0}^n{n \choose i}1^{n-i}2^i \\ &= \sum_{i=0}^n{n \choose i}2^i \end{align} $$

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

  • $\begingroup$ To make the answer match the question you can go on with the counting argument re. choices of items for the different terms in the sum. $\endgroup$ – user48672 Nov 27 '16 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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