3
$\begingroup$

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
    @MichaelJoyce: I would nuance the remark about learning combinatorics. I think it is OK to give an algebraic proo$f$ 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".2012-09-20

2 Answers 2

7

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.

  • 0
    $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$.2012-09-20
0

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 $

  • 0
    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.2016-11-27