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.

I need help proving that $$\sum_{r=0}^n\binom{n}{r}2^r=3^n$$

I'm thinking this should use the idea that $\binom{n}{r}=\binom{n}{n-r}$ but I'm not sure how to proceed with it.

Thanks in advance!

share|improve this question
add comment

4 Answers

up vote 5 down vote accepted

${n \choose r}$ is the number of $r$-element subsets of $n$-element set.
$\sum_{r=0}^{n}{n \choose r}$ - number of all subsets of $n$-element set, so $\sum_{r=0}^{n}{n \choose r}=2^n$ (why?).
$2^r$ - number of all subsets of $r$-element set.
What we can say now about: $\sum_{r=0}^{n}{n \choose r}2^r$?

share|improve this answer
add comment

Hint: Expand $(1+2)^n$ in the usual way.

The result is a special case of a familiar result.

share|improve this answer
    
Is it the power series? or am I way off? –  jldavis76 Dec 13 '12 at 16:36
    
It is the Binomial Theorem $(a+b)^n=\dots$ using $a=1$, $b=2$, or more or less equivalently the (finite) series expansion for $(1+x)^n$. MarkT has a nice answer that bypasses the Binomial Theorem and gives a direct combinatorial proof. –  André Nicolas Dec 13 '12 at 16:42
    
Actually, the definition of binomial coefficoent (at least the one that explains the name) immediately gives that the binomial $(1+x)^n$ can be computed via the polynomial $\sum{n\choose k}x^k$. In this sense, "bypassing" the binomial theorem is less direct. –  Hagen von Eitzen Dec 13 '12 at 17:08
    
@HagenvonEitzen: True, but the real name for something like $\binom{n}{k}$ is Choose Symbol. –  André Nicolas Dec 13 '12 at 17:28
    
@AndréNicolas Hm, is that true? I'm not a native speaker and my comment may have been based on the usual naming in German. On the other hand, I find e.g no Wikipedia entry for choose symbol ... –  Hagen von Eitzen Dec 13 '12 at 21:47
show 2 more comments

from binomial theorem $$(1+t)^n=\sum_{r=0}^n\binom{n}{r}t^r$$ for $t=2$ we get $$(1+2)^n=\sum_{r=0}^n\binom{n}{r}2^r$$ or $$\sum_{r=0}^n\binom{n}{r}2^r=3^n$$

share|improve this answer
add comment

Suppose you have $n$ objects, and you want to divide them into three sets.

You can do it in two ways:

  • For each object, choose whether to put it into set $A$, or set $B$, or set $C$. There are $3$ choices for each of the $n$ objects, so $3^n$ ways total.

  • First choose some number of objects (say $r$) for set $A$ (this you can do in $\binom{n}{r}$ ways), then, for each of the remaining $n-r$ objects, choose whether to put it in set $B$ or set $C$ ($2$ choices for each of $n-r$ objects, so $2^{n-r}$ ways).

So: $$3^n = \sum_{r=0}^{n} \binom{n}{r} 2^{n-r}$$

Why this is the same as your expression I leave it to you to figure out. :-) [Hint: $\binom{n}{r} = \binom{n}{n-r}$.]

share|improve this answer
add comment

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.