# Mathematical Induction

• Jul 19th 2007, 11:01 AM
storchfire1X
Mathematical Induction
Hi I hope someone can help me with this problem:

Prove the following formula by induction:

1+(1/2)+(1/4)+(1/8)+...+1/(2^n) = 2 - 1/(2^n)

• Jul 19th 2007, 11:08 AM
CaptainBlack
Quote:

Originally Posted by storchfire1X
Hi I hope someone can help me with this problem:

Prove the following formula by induction:

1+(1/2)+(1/4)+(1/8)+...+1/(2^n) = 2 - 1/(2^n)

A) Base case n=0, then the left hand side is 1, and the right hnd side is 1.

B) Suppose this true for some $n=k \in \mathbb{N_+}$

Then:

$
[1+1/2+1/4+1/8+...+1/2^{k}]+1/2^{k+1} = [2 - 1/2^k]+1/2^{k+1} = 2-1/2^{k+1}
$

hence it is true for k+1.

Thus combining A), and B) we have proven that it is true for all $n \in \mathbb{N}$ by mathematical induction

RonL
• Jul 19th 2007, 11:14 AM
topsquark
Quote:

Originally Posted by storchfire1X
Hi I hope someone can help me with this problem:

Prove the following formula by induction:

1+(1/2)+(1/4)+(1/8)+...+1/(2^n) = 2 - 1/(2^n)

n = 0

$1 = 2 - \frac{1}{2^0} = 2 - 1 = 1$ (Check!)

Now assume this is true for some n = k. We wish to show that it is true for n = k + 1.

So assume:
$1 + \frac{1}{2} + ~ ... ~ + \frac{1}{2^k} = 2 - \frac{1}{2^k}$
is true.

$1 + \frac{1}{2} + ~ ... ~ + \frac{1}{2^k} + \frac{1}{2^{k + 1}}$

$= \left ( 2 - \frac{1}{2^k} \right ) + \frac{1}{2^{k + 1}}$

$= 2 - \left ( \frac{1}{2^k} - \frac{1}{2^{k + 1}} \right )$

$= 2 - \left ( \frac{1}{2^k} - \frac{1}{2} \cdot \frac{1}{2^k} \right )$

$= 2 - \left ( 1 - \frac{1}{2} \right ) \frac{1}{2^k}$

$= 2 - \frac{1}{2} \cdot \frac{1}{2^k}$

$= 2 - \frac{1}{2^{k + 1}}$
as we needed to show.

-Dan