# Manipulating Sums

• Oct 21st 2010, 11:59 AM
evanator
Manipulating Sums
Hi there,

I am trying to solve the following problem. I have gotten a fair way into it, but the last steps elude me. Here is the problem:

Show that $\displaystyle \displaystyle\sum_{r=0}^n ^nC_r 2^r = 3^n$

So, we already know that $\displaystyle \displaystyle\sum_{r=0}^n ^nC_r = 2^n$, because

$\displaystyle (a+b)^n = \displaystyle\sum_{r=0}^n ^nC_r a^{n-r} b^{r}$

Letting $\displaystyle a = 1$ and $\displaystyle b = 1$:

$\displaystyle (1+1)^n = \displaystyle\sum_{r=0}^n ^nC_r 1^{n-r} 1^{r}$

$\displaystyle 2n = \displaystyle\sum_{r=0}^n ^nC_r$

Getting back to the matter at hand, we can take out the $\displaystyle 2^n$:

$\displaystyle 2^n \displaystyle\sum_{r=0}^n 2^r$

We can also write it as:

$\displaystyle \displaystyle\sum_{r=0}^n 2^{n+r}$

This gives the same series, because

$\displaystyle (2^n \times 2^0) + (2^n \times 2^1) + (2^n \times 2^2) + ... + (2^n \times 2^n)$

is the same as

$\displaystyle 2^{n+0} + 2^{n +1} + 2^{n+2} + ... + 2^{2n}$

I don't know what to do to get the $\displaystyle 3^n$ though.
Any help would be appreciated.

Regards,

Evanator
• Oct 21st 2010, 12:01 PM
Plato
Notice that $\displaystyle 3^n=(1+2)^n$. Just expand.
• Oct 21st 2010, 12:15 PM
evanator
Looks like I couldn't see the wood for the trees. Thank you, Plato.
Expanding out, bearing in mind that $\displaystyle (1+2)^n = 3^n$:

$\displaystyle (a+b)^n = \displaystyle\sum_{r=0}^n ^nC_r a^{n-r} b^r$

$\displaystyle (1+2)^n = \displaystyle\sum_{r=0}^n ^nC_r 1^{n-r} 2^r$

$\displaystyle 3^n = \displaystyle\sum_{r=0}^n ^nC_r 2^r$