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