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.
Best Answer
Yes, I agree with your interpretation of the left side, and also lhf's comment can be seen in the same way: