Combinatorial proof of $\sum\limits_{k=0}^n {n \choose k}3^k=4^n$
Yes, I agree with your interpretation of the left side, and also lhf's comment can be seen in the same way:
- $4^n$ the ways of divide $n$ balls in $4$ boxes
- $(3+1)^n$ the same as above
- $ \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
- $\sum_{k=0}^n {n \choose k}3^k$ as above, using $1^{n-k}=1$