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!
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!
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}$.]
Hint: Expand $(1+2)^n$ in the usual way.
The result is a special case of a familiar result.
${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$?
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$