5
$\begingroup$

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!

$\endgroup$

4 Answers 4

8
$\begingroup$

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

The result is a special case of a familiar result.

$\endgroup$
7
  • $\begingroup$ Is it the power series? or am I way off? $\endgroup$
    – jldavis76
    Commented Dec 13, 2012 at 16:36
  • $\begingroup$ 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. $\endgroup$ Commented Dec 13, 2012 at 16:42
  • $\begingroup$ 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. $\endgroup$ Commented Dec 13, 2012 at 17:08
  • $\begingroup$ @HagenvonEitzen: True, but the real name for something like $\binom{n}{k}$ is Choose Symbol. $\endgroup$ Commented Dec 13, 2012 at 17:28
  • $\begingroup$ @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 ... $\endgroup$ Commented Dec 13, 2012 at 21:47
7
$\begingroup$

${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$?

$\endgroup$
7
$\begingroup$

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$$

$\endgroup$
6
$\begingroup$

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}$.]

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .