# Weird $3^n$ in an identity to be combinatorially proved

Give a combinatorial proof of the following identity:

$$3^n=\sum_{i=0}^{n}\binom{n}{i}2^{n-i}$$

I can't see any counting argument that would yield $3^n$, and the right hand side is also pretty opaque. For some reason I really really suck at doing these proofs - I just started my first combinatorics course.

• This is the Newton binomial for $(2+1)^n$ – Ewan Delanoy May 11 '13 at 14:48
• just take out $2^n$ and use Binomial theorem – Alex May 11 '13 at 14:52
• I want a combinatorics proof which means no algebraic rearranging of the stuff. – ithisa May 11 '13 at 14:59
• @EricDong It might help to modify your question as "I want a proof by a combinatorial argument" to get better responses. – user75930 May 11 '13 at 15:13

Suppose you have $n$ balls to be put into 3 boxes. You may keep any or all boxes empty.Then the number of ways of putting $n$ balls into 3 boxes is $3^n$. For the right hand side of the equation, you may fix a box $C$. The box $C$ may contain $0,1,2,\dots n$ balls. If the box $C$ has $i$ balls, you may choose the $i-\text{balls}$ to be put into $C$ in $\binom{n}{i}$ ways and the remaining $n-i$ balls may be put into boxes A or B in $2^{n-i}$ ways. Hence the number of ways of putting $n$ balls into 3 boxes is $\displaystyle \sum_{i=0}^n \binom{n}{i}2^{n-i}$ ways and hence $$3^n=\displaystyle \sum_{i=0}^n \binom{n}{i}2^{n-i}.$$ Please let me know if my solution is incorrect.
$$(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k$$
Hint: Color $n$ balls with 3 colors.