5
$\begingroup$

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.

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

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.

$\endgroup$
2
$\begingroup$

Hints:

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

$\endgroup$
1
$\begingroup$

Hint: Color $n$ balls with 3 colors.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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