Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
5  
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
1  
I want a combinatorics proof which means no algebraic rearranging of the stuff. –  user54609 May 11 '13 at 14:59
1  
@EricDong It might help to modify your question as "I want a proof by a combinatorial argument" to get better responses. –  Sabyasachi Mukherjee May 11 '13 at 15:13

3 Answers 3

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.

share|improve this answer

Hints:

$$(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k$$

share|improve this answer

Hint: Color $n$ balls with 3 colors.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.