# Proving Identities

• Sep 13th 2010, 05:45 PM
taylor1234
Proving Identities
Prove the following identities

1*2^0 + 2*2^1 + 3*2^2 + . . . + n*2^2n-1= (n-1)2^n + 1

Also

1 + 3 + 9 + 27 + . . . + 3^n-1= (3n-1)
2
• Sep 13th 2010, 05:51 PM
Prove It
I assume the second one should be

$\displaystyle 1 + 3 + 9 + 27 + \dots + 3^{n - 1} = \frac{3^n - 1}{2}$.

This is a geometric series with $\displaystyle a = 1, r = 3$.

So $\displaystyle S_n = \frac{a(r^n - 1)}{r - 1}$

$\displaystyle = \frac{1(3^n - 1)}{3 - 1}$

$\displaystyle = \frac{3^{n + 1} - 1}{2}$.
• Sep 13th 2010, 08:05 PM
Soroban
Hello, taylor1234!

There is a typo in the first one . . . the general term is not correct.

Quote:

$\displaystyle 1\cdot2^0 + 2\cdot2^1 + 3\cdot2^2 + \hdots + \underbrace{n\cdot2^{2n-1}}_{???} \;=\; (n-1)2^n + 1$

In each term, the exponent is one less than the coefficient: .$\displaystyle a_n \:=\:n\cdot 2^{n-1}$

We have: . . . . .$\displaystyle S \;=\; 1\!\cdot\!2^0 + 2\!\cdot\!2^1 + 3\!\cdot\!2^2 + 4\!\cdot\!2^3 + \hdots + n\!\cdot\!2^{n-1}\qquad\qquad\qquad[1]$

Multiply by 2: . $\displaystyle 2S \;=\; \qquad \quad 1\!\cdot\!2^1 + 2\!\cdot\12^2 + 3\!\cdot\!2^3 + \hdots + (n-1)2^{n-1} + n\!\cdot\!2^n \;\;[2]$

Subtract [2] - [1]: .$\displaystyle S \;=\;-1 - 2 - 2^2 - 2^3 - \hdots - 2^{n-1} + n\cdot2^n$

. . . . . . . . . . . . . $\displaystyle S \;=\;-\underbrace{(1 + 2 + 2^2 + 2^3 + \hdots 2^{n-1})}_{\text{geometric series}} +\; n\cdot 2^n$

. . . . . . . . . . . . .$\displaystyle S \;=\;-\left(\dfrac{2^n-1}{2-1}\right) + n\cdot 2^n$

. . . . . . . . . . . . .$\displaystyle S \;=\;-(2^n - 1) + n\cdot2^n$

. . . . . . . . . . . . .$\displaystyle S \;=\;-2^n + 1 + n\cdot2^n$

. . . . . . . . . . . . .$\displaystyle S \;=\;(n-1)2^n + 1$
• Sep 14th 2010, 07:16 AM
taylor1234
How would I solve these problems using the induction method. Assuming Sn is true and testing for Sn+1?