# Combinatorial proof of $\sum\limits_{k=0}^n {n \choose k}3^k=4^n$

Using the following equation:

$$\sum_{k=0}^n {n \choose k}3^k=4^n$$

I need to prove that both sides of the equation solve the same combinatorial problem.

It's easy to see that the right side of the equation is counting number of ways to divide $n$ different balls into $4$ buckets.

Is it correct to say that the left side of the equation solve the same problem the following way (?):

Since $\sum\limits_{k=0}^n {n \choose k} 3^k= \sum\limits_{k=0}^n {n \choose n-k}3^k$, we can change the equation to:

$$\sum_{k=0}^n {n \choose n-k}3^k=4^n$$

And from the new equation, it is easier to see that each binomial coefficient chooses number of balls to put in the first bucket, and $3^k$ divides the rest $k$ balls between the rest 3 buckets without limitation.

-
I assume you don't want this: $\sum_{k=1}^n {n \choose k}3^k= \sum_{k=1}^n {n \choose k} 1^{n-k} 3^k=(1+3)^n = 4^n$... – lhf Sep 23 '11 at 11:33
Thanks @lhf, but no, i'm just looking for Combinatorical explanation. – MichaelS Sep 23 '11 at 11:35
@MichaelS: Your combinatorial argument is simple and correct. – Christian Blatter Sep 23 '11 at 11:49
@ChristianBlatter, Thanks! Happy to see i got it right.. – MichaelS Sep 23 '11 at 12:13
Everything is fine. For myself, I prefer to count the words of length $n$ over the alphabet $\{1,2,3,4\}$. Same analysis. – André Nicolas Sep 23 '11 at 14:24

1. $4^n$ the ways of divide $n$ balls in $4$ boxes
2. $(3+1)^n$ the same as above
3. $\sum_{k=0}^n {n \choose k} 1^{n-k} 3^k$ for every $k$, the ways to choose $k$ balls among the $n$ balls you have, times the ways to put $n-k$ balls in a box, times the ways to put the remaining $k$ balls in the remaining $3$ boxes
4. $\sum_{k=0}^n {n \choose k}3^k$ as above, using $1^{n-k}=1$