Associated Topics || Dr. Math Home || Search Dr. Math

### Proof by Induction

```Date: 03/18/2003 at 05:01:37
From: TEA
Subject: Sum

Hello,

What is the expression for:

n
----
\
/     2 to the power of r
----
r=0

How can we prove it?

Thanks,
Tony
```

```
Date: 03/18/2003 at 07:07:08
From: Doctor Jeremiah
Subject: Re: Sum

Hi Tony,

Write out the sum:

2^0 + 2^1 + 2^2 + 2^3 + 2^4 + ...
1  +  2  +  4  +  8  +  16 + ...

The sum of the first 2 terms equals  3 and the 3rd term is 4
The sum of the first 3 terms equals  7 and the 4th term is 8
The sum of the first 4 terms equals 15 and the 5th term is 16

See the pattern?  If you want to prove it I think induction
is the best way.

There is a good explanation of induction in the archives:

Sum of n Odd Numbers
http://mathforum.org/library/drmath/view/56866.html

What we want to prove is that the sum of the first n terms is the n+1
term's value minus one. Written mathematically we are trying to prove:

n
-----
\
/    2^r = 2^(n+1)-1
-----
r=0

Induction has three steps:
1) Prove it's true for one value.
2) Prove it's true for the next value.

The way we do step 2 is assume it's true for some arbitrary value (in
this case k). We know it's true for one arbitrary value of k because
of the base case. So if we can prove it's true for k+1, then we have
proven it for all arbitrary values.

Step 1:  Base case n=0

n
-----
\
/    2^r = 2^0 = 1 = 2^1 - 1           TRUE
-----
r=0

Step 2:  Assume it's true for n=k

k
-----
\
/    2^r = 2^(k+1)-1                   ASSUMED
-----
r=0

Step 3:  Try to prove n=k+1

k+1
-----
\
/    2^r = 2^((k+1)+1)-1
-----
r=0

k
-----
\
/    2^r   + 2^(k+1) = 2^(k+2)-1
-----
r=0

At this point we can substitute our assumption.
If we prove this is true, that validates the assumption
and all is fine.

2^(k+1)-1 + 2^(k+1) = 2^(k+2)-1
2*2^(k+1)-1 = 2^(k+2)-1
2^((k+1)+1)-1 = 2^(k+2)-1
2^(k+2)-1 = 2^(k+2)-1                   TRUE

The assumption is true and the proof therefore is true.

- Doctor Jeremiah, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search